Advanced

Approximating Longest Path

Björklund, Andreas LU (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:
author
supervisor
organization
publishing date
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 &gt; 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 &gt; 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},
}