Approximating Longest Path
(2003)- Abstract
- We investigate the computational hardness of approximating the longest path and the longest cycle in undirected and directed graphs on n vertices. We show that
* in any expander graph, we can find (n) long paths in polynomial time.
* there is an algorithm that finds a path of length (log2 L/ log log L) in any undirected graph having a path of length L, in polynomial time.
* there is an algorithm that finds a path of length (log2 n/ log log n) in any Hamiltonian directed graph of constant bounded outdegree, in polynomial time.
* there cannot be an algorithm finding paths of length (n ) for any constant > 0 in a Hamiltonian directed graph of bounded outdegree in polynomial time, unless P = NP.
... (More) - We investigate the computational hardness of approximating the longest path and the longest cycle in undirected and directed graphs on n vertices. We show that
* in any expander graph, we can find (n) long paths in polynomial time.
* there is an algorithm that finds a path of length (log2 L/ log log L) in any undirected graph having a path of length L, in polynomial time.
* there is an algorithm that finds a path of length (log2 n/ log log n) in any Hamiltonian directed graph of constant bounded outdegree, in polynomial time.
* there cannot be an algorithm finding paths of length (n ) for any constant > 0 in a Hamiltonian directed graph of bounded outdegree in polynomial time, unless P = NP.
* there cannot be an algorithm finding paths of length (log2+ n), or cycles of length (log1+ n) for any constant > 0 in a Hamiltonian directed graph of constant bounded outdegree in polynomial time, unless 3-Sat can be solved in subexponential time. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/957757
- author
- Björklund, Andreas ^{LU}
- supervisor
- organization
- publishing date
- 2003
- type
- Thesis
- publication status
- published
- subject
- pages
- 25 pages
- language
- English
- LU publication?
- yes
- id
- eb50c046-f65e-4fe1-9ded-c948191fac21 (old id 957757)
- date added to LUP
- 2008-01-31 11:35:28
- date last changed
- 2016-09-19 08:45:19
@misc{eb50c046-f65e-4fe1-9ded-c948191fac21, abstract = {We investigate the computational hardness of approximating the longest path and the longest cycle in undirected and directed graphs on n vertices. We show that<br/><br> * in any expander graph, we can find (n) long paths in polynomial time.<br/><br> * there is an algorithm that finds a path of length (log2 L/ log log L) in any undirected graph having a path of length L, in polynomial time.<br/><br> * there is an algorithm that finds a path of length (log2 n/ log log n) in any Hamiltonian directed graph of constant bounded outdegree, in polynomial time.<br/><br> * there cannot be an algorithm finding paths of length (n ) for any constant > 0 in a Hamiltonian directed graph of bounded outdegree in polynomial time, unless P = NP.<br/><br> * there cannot be an algorithm finding paths of length (log2+ n), or cycles of length (log1+ n) for any constant > 0 in a Hamiltonian directed graph of constant bounded outdegree in polynomial time, unless 3-Sat can be solved in subexponential time.}, author = {Björklund, Andreas}, language = {eng}, pages = {25}, title = {Approximating Longest Path}, year = {2003}, }