Approximating longest directed paths and cycles
(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:
https://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
- 1611-3349
- DOI
- 10.1007/b99859
- language
- English
- LU publication?
- yes
- id
- be3a19fc-120f-4f37-a41d-80bfe4fbe269 (old id 267208)
- date added to LUP
- 2016-04-01 12:03:22
- date last changed
- 2022-01-26 22:07:27
@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}},
doi = {{10.1007/b99859}},
volume = {{3142}},
year = {{2004}},
}