ECCC-Report TR03-032https://eccc.weizmann.ac.il/report/2003/032Comments and Revisions published for TR03-032en-usWed, 30 Apr 2003 14:44:37 +0300
Paper TR03-032
| Approximating Longest Directed Path |
Andreas Björklund,
Thore Husfeldt,
Sanjeev Khanna
https://eccc.weizmann.ac.il/report/2003/032 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.
Wed, 30 Apr 2003 14:44:37 +0300https://eccc.weizmann.ac.il/report/2003/032