14
$\begingroup$

The longest path problem is NP-hard. The (typical?) proof relies on a reduction of the Hamiltonian path problem (which is NP-complete). Note that here the path is taken to be (node-)simple. That is, no vertex can occur more than once in the path. Obviously it is thus also edge-simple (no edge will occur more than once in the path).

So what if we drop the requirement of finding a (node-)simple path and stick to finding an edge-simple path (trail). At first glance, since finding a Eulerian trail is much easier than finding a Hamiltonian path, one might have some hope that finding the longest trail would be easier than finding the longest path. However, I cannot find any reference proving this, let alone one that provides an algorithm.

Note that I am aware of the argument made here: https://stackoverflow.com/questions/8368547/how-to-find-the-longest-heaviest-trail-in-an-undirected-weighted-graph However, the argument seems flawed in its current form, as it basically shows you could solve the edge-simple case by solving the node-simple case on a different graph (so the reduction is the wrong way around). It is not clear that the reduction could easily be changed to work the other way as well. (Still, it does show that at the very least the longest trails problem is not harder than the longest paths problem.)

So are there any known results for finding longest trails (edge-simple paths)? Complexity (class)? (Efficient) algorithm?

Improve this question
$\endgroup$
14
  • $\begingroup$ This is not the exact same problem, but take a look at the Minimum Euilerian Extension problem which is quite similar. $\endgroup$
    – R B
    Jan 22, 2014 at 12:39
  • 10
    $\begingroup$ Perhaps I didn't understand well the question, but Hamiltonian path is NP-complete even on cubic graphs, since every traversal of a node requires two edges there is no way to reuse a node twice even if we relax the condition from node-simple paths to edge-simple paths; so the Hamiltonian path problem remains NP-complete. $\endgroup$
    – Marzio De Biasi
    Jan 22, 2014 at 13:56
  • 3
    $\begingroup$ @Bangye: ok but in cubic graphs if a node is traversed once, then 2 edges must be used ... and the node cannot be traversed again (because there is only one untraversed edge). So in cubic graphs the nodes cannot be "repeated" (except for the last edge of the trail that can be incident to an already traversed node) $\endgroup$
    – Marzio De Biasi
    Jan 22, 2014 at 14:11
  • 1
    $\begingroup$ Here is the reference: A.A. Bertossi, The edge hamiltonian path problem is NP-complete, Information Process- ing Letters, 13 (1981) 157-159. $\endgroup$
    – Lamine
    Jan 22, 2014 at 15:54
  • 1
    $\begingroup$ @Lamine: Thanks for the clarification. I don't think you have to delete your comments because it would be very natural to come up with a similar idea first and seeing it doesn't work is really helpful. $\endgroup$
    – Yota Otachi
    Jan 23, 2014 at 11:37

1 Answer 1

Reset to default
21
$\begingroup$

From the comments above: the Hamiltonian cycle problem remains NP-complete even in grid graphs with max degree 3 [1], but in these graphs every traversal of a node requires two edges and at most one edge remains unused, so a node cannot be traversed twice by an Eulerian path.

So apparently there is an immediate reduction from the Hamiltonian cycle problem to your problem: given a grid graph with max degree 3 $G = (V,E)$, just ask for a trail of length $|V|$.

But all three edges of the node at the end of the trail can be used; to avoid this situation you can pick the top-left node $u$ of the grid graph (which has degree two) and add two nodes: $V' = V \cup \{u',u''\}$ and a new edges $E = E \cup \{(u,u'), (u,u'')\}$ and ask for a trail of length $|V'| = |V|+2$: informally the added edge forces $u',u''$ to be the endpoints of the trail.

[1] Christos H Papadimitriou, Umesh V Vazirani, On two geometric problems related to the travelling salesman problem, Journal of Algorithms, Volume 5, Issue 2, June 1984, Pages 231-246, ISSN 0196-6774

Improve this answer
$\endgroup$
2
  • $\begingroup$ I'm having a little trouble marrying this, as well as some of the other comments, to the known ease of finding a Eulerian trail. Or is the crucial point that (sticking to your example) deciding whether or not there is a "Eulerian" trail of length $|E|$ is easier than deciding whether or not there is a trail of length $|V|$? This would certainly be a bit of a surprise to me, but definitely interesting. $\endgroup$
    – Jasper
    Jan 30, 2014 at 9:05
  • 1
    $\begingroup$ In cubic graphs you are sure that there is not a trail of length $|E|$ , indeed all edges have odd degree 3 ($O(1)$ complexity). So the problems of finding a trail of length $|V|$ (with the additional trick $u',u''$) is harder (NPC); informally: for every node there are three pairs of edges that can be used to buid the trail, and you don't know the "effects" of a choice until you build the rest of the trail. In a normal graph the Eulerian path is easy to calculate because at every step you can be sure that you can "return back" to the starting node (see Fleury's algorithm). $\endgroup$
    – Marzio De Biasi
    Jan 30, 2014 at 9:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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