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 3Sat 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

 Thore Husfeldt ^{LU}
 organization
 publishing date
 2003
 type
 Thesis
 publication status
 published
 subject
 pages
 25 pages
 language
 English
 LU publication?
 yes
 id
 eb50c046f65e4fe19dedc948191fac21 (old id 957757)
 date added to LUP
 20080131 11:35:28
 date last changed
 20160919 08:45:19
@misc{eb50c046f65e4fe19dedc948191fac21, 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 3Sat can be solved in subexponential time.}, author = {Björklund, Andreas}, language = {eng}, note = {Licentiate Thesis}, pages = {25}, title = {Approximating Longest Path}, year = {2003}, }