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:
https://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
- 2016-04-04 14:29:38
- date last changed
- 2021-05-06 20:22:13
@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}}, note = {{Licentiate Thesis}}, title = {{Approximating Longest Path}}, url = {{https://lup.lub.lu.se/search/files/6373191/965291.pdf}}, year = {{2003}}, }