Approximating Longest Directed Paths and Cycles

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. Assuming the stronger complexity conjecture that Satisfiability cannot be solved in subexponential time, we show that there is no polynomial time algorithm that finds a directed path of length Ω(f(n) log2n), or a directed cycle of length Ω(f(n) log n), for any nondecreasing, polynomial time computable function f in Ω(1). With a recent algorithm for undirected graphs by Gabow, this shows that long paths and cycles are harder to find in directed graphs than in undirected graphs. We also find a directed path of length Ω(log2 n/ log log n) in Hamiltonian digraphs with bounded outdegree. With our hardness results, this shows that long directed cycles are harder to find than a long directed paths. Furthermore, we present a simple polynomial time algorithm that finds paths of length Ω(n) in directed expanders of constant bounded outdegree.  ), pages 222-233. Publisher URL: http://dx.doi.org/10.1007/b99859 This conference paper is available at ScholarlyCommons: http://repository.upenn.edu/cis_papers/205 Approximating Longest Directed Paths and Cycles Andreas Björklund, Thore Husfeldt, and Sanjeev Khanna 1 Department of Computer Science, Lund University, Box 118, 221 00 Lund, Sweden. thore@cs.lu.se 2 Dept. of CIS, University of Pennsylvania, Philadelphia, PA 19104.  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. 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. Assuming the stronger complexity conjecture that Satisfiability cannot be solved in subexponential time, we show that there is no polynomial time algorithm that finds a directed path of length Ω(f(n) log n), or a directed cycle of length Ω(f(n) log n), for any nondecreasing, polynomial time computable function f in ω(1). With a recent algorithm for undirected graphs by Gabow, this shows that long paths and cycles are harder to find in directed graphs than in undirected graphs. We also find a directed path of length Ω(log n/ log log n) in Hamiltonian digraphs with bounded outdegree. With our hardness results, this shows that long directed cycles are harder to find than a long directed paths. Furthermore, we present a simple polynomial time algorithm that finds paths of length Ω(n) in directed expanders of constant bounded outdegree.