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
- 2025-04-04 14:06:52
@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}},
}