Approximating Longest Directed Path
Andreas Björklund, Thore Husfeldt, Sanjeev Khanna · 2003
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 n1 for any > 0 unless P = NP. In particular, the result holds for digraphs of constant bounded outdegree that contain a Hamiltonian cycle. As-suming the stronger complexity conjecture that Satisability cannot be solved in subexponential time, we show that there is no polynomial time algorithm that always nds a path of length (log2+ n), or a cycle of length (log1+ n), for any constant > 0 in these graphs. In contrast we show that there is a polynomial time algorithm always nding a path of length (log2 n = log log n) in these graphs. This separates the approxima-tion hardness of Longest Path and Longest Cycle in this class of graphs. Furthermore, we present a polynomial time algorithm that nds paths of length (n) in most digraphs of constant bounded outdegree. 1