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.

  • $\begingroup$ I presume you are given the initial and final vertices. If so, I suspect you'll need to use a traditional branch-and-bound or tree search algorithm such as $A^*$, since even a single edge can make a path's length maximal. $\endgroup$ – David G. Stork Jul 16 '18 at 18:30
  • 2
    $\begingroup$ if this was possible in polynomial time then we would be able to check if a graph is hamiltonian in polynomial time. $\endgroup$ – Jorge Fernández Hidalgo Jul 16 '18 at 18:44
  • $\begingroup$ @JorgeFernández I forgot to write that those 2 vertices are given. Thank you for correction DavidG.Stork $\endgroup$ – User5468622 Jul 16 '18 at 19:14
  • $\begingroup$ it does not matter $\endgroup$ – Jorge Fernández Hidalgo Jul 16 '18 at 19:17
  • $\begingroup$ What kind of approximation error would be appropriate? $\endgroup$ – Sudix Jul 16 '18 at 19:31

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.]

  • $\begingroup$ Thank you for your answer. Do you know any approximation to this problem ? $\endgroup$ – User5468622 Jul 17 '18 at 18:49
  • $\begingroup$ ac.els-cdn.com/S0196677403000932/… $\endgroup$ – Mike Jul 18 '18 at 16:12
  • $\begingroup$ I used google to find this. But from this link it looks like even finding a path of length $\Omega(\log^2 n)$ where $n$ is the number of vertices, looks quite challenging, for general graphs. But for "real-world" applications and graphs not so large, maybe a heuristic would do? Depends on the size/additional structure you can glean from the graphs. $\endgroup$ – Mike Jul 18 '18 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.