TR03-032 Authors: Andreas Björklund, Thore Husfeldt, Sanjeev Khanna

Publication: 30th April 2003 14:44

Downloads: 3011

Keywords:

We investigate the hardness of approximating the longest path and

the longest cycle in directed graphs on $n$ vertices. We show that

neither of these two problems can be polynomial time approximated

within $n^{1-\epsilon}$ for any $\epsilon>0$ unless

$\text{P}=\text{NP}$. In particular, the result holds for

digraphs of constant bounded outdegree that

contain a Hamiltonian cycle. Assuming the stronger complexity

conjecture that Satisfiability cannot be solved in subexponential

time, we show that there is no polynomial time algorithm that always

finds a path of length $\Omega(\log^{2+\epsilon} n)$, or a cycle of

length $\Omega(\log^{1+\epsilon} n)$, for any constant $\epsilon>0$

in these graphs. In contrast we show that there is a polynomial time

algorithm always finding a path of length $\Omega(\log^2 n/\log\log

n)$ in these graphs. This separates the approximation hardness of

Longest Path and Longest Cycle in this class of graphs. Furthermore,

we present a polynomial time algorithm that finds paths of length

$\Omega(n)$ in most digraphs of constant bounded outdegree.