Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR03-032 | 16th April 2003 00:00

Approximating Longest Directed Path


Authors: Andreas Björklund, Thore Husfeldt, Sanjeev Khanna
Publication: 30th April 2003 14:44
Downloads: 2152


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.

ISSN 1433-8092 | Imprint