Advanced

Approximating longest directed paths and cycles

Björklund, Andreas LU ; Husfeldt, Thore LU and Khanna, S (2004) In Lecture Notes in Computer Science 3142. p.222-233
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(1-epsilon)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(1-epsilon)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:
author
organization
publishing date
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
1611-3349
DOI
10.1007/b99859
language
English
LU publication?
yes
id
be3a19fc-120f-4f37-a41d-80bfe4fbe269 (old id 267208)
date added to LUP
2007-08-02 10:55:54
date last changed
2017-09-03 03:45:54
@article{be3a19fc-120f-4f37-a41d-80bfe4fbe269,
  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(1-epsilon)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         = {1611-3349},
  language     = {eng},
  pages        = {222--233},
  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},
}