Approximating Longest Path

Sammanfattning: 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.