Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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
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 &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}},
  note         = {{Licentiate Thesis}},
  title        = {{Approximating Longest Path}},
  url          = {{https://lup.lub.lu.se/search/files/6373191/965291.pdf}},
  year         = {{2003}},
}