Consider undirected unweighted graph. My problem is to find the longest simple path between two given vertices or its approximation.
I was thinking of solution like this – Find the shortest simple path using Dijkstra's algorithm. For every 2 vertices, which are neighbors on that path, simulate that edge between them is missing and try to find another path between them using Dijkstra's algorithm. Then apply it again on newly created path until we are not able to increase size of the path.
I think that this would work but it has very high time complexity.
Can anyone help me with better algorithm or does anyone know any approximation to this problem ?
Thank you.
Best Answer
This (finding the longest path between two vertices in a graph even with the length of each edge being 1 or $-\infty$) is NP-hard though.
If you could do this, then you could find whether the resulting graph has a Hamiltonian path. (If $G$ has a Hamiltonian path, then for one of the only $O(n^2)$ pairs of vertices $u$ and $v$, there is a path w $n$ vertices starting at $u$ and ending at $v$.) OR in fact a Hamiltonian cycle. (If $G$ has a Hamiltonian cycle, then for one of the only $O(n^2)$ edges $uv$ of $G$, there is a path w $n$ vertices starting at $u$ and ending at $v$ in $G \setminus \{uv\}$.)
See also:
Finding a longest path on a weighted graph - solvable deterministically and in polynomial time?
[I thought this question sounded familiar, I gave the same answer here too.]