Approximating longest directed paths and cycles
(2004) In Lecture Notes in Computer Science 3142. p.222233 Abstract
 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(1epsilon)for any epsilon > 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 Omega(f(n) log(2) n), or a directed cycle of length Omega(f(n) log n), for any nondecreasing, polynomial time computable function f in w(1). With a recent algorithm for undirected graphs by... (More)
 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(1epsilon)for any epsilon > 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 Omega(f(n) log(2) n), or a directed cycle of length Omega(f(n) log n), for any nondecreasing, polynomial time computable function f in w(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 Omega(log(2) 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 Omega(n) in directed expanders of constant bounded outdegree. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/267208
 author
 Björklund, Andreas ^{LU} ; Husfeldt, Thore ^{LU} and Khanna, S
 organization
 publishing date
 2004
 type
 Contribution to journal
 publication status
 published
 subject
 in
 Lecture Notes in Computer Science
 volume
 3142
 pages
 222  233
 publisher
 Springer
 external identifiers

 wos:000223656400021
 scopus:35048842055
 ISSN
 16113349
 DOI
 10.1007/b99859
 language
 English
 LU publication?
 yes
 id
 be3a19fc120f4f37a41d80bfe4fbe269 (old id 267208)
 date added to LUP
 20070802 10:55:54
 date last changed
 20170903 03:45:54
@article{be3a19fc120f4f37a41d80bfe4fbe269, abstract = {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(1epsilon)for any epsilon > 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 Omega(f(n) log(2) n), or a directed cycle of length Omega(f(n) log n), for any nondecreasing, polynomial time computable function f in w(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 Omega(log(2) 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 Omega(n) in directed expanders of constant bounded outdegree.}, author = {Björklund, Andreas and Husfeldt, Thore and Khanna, S}, issn = {16113349}, language = {eng}, pages = {222233}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Approximating longest directed paths and cycles}, url = {http://dx.doi.org/10.1007/b99859}, volume = {3142}, year = {2004}, }