<p>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.</p>

<p>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|$.</p>

<p>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.</p>

<p>[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</p>

CC BY-SA 3.0
2014-01-30T09:05:34.080Z
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.
Jasper
CC BY-SA 3.0
2014-01-30T09:58:26.647Z
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).
Marzio De Biasi
CC BY-SA 3.0
2014-01-22T16:18:22.833Z
2014-01-22T16:30:36.117Z
2014-01-22T16:30:36.117Z
Marzio De Biasi
<p>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).</p>

<p>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.</p>

<p>Note that I am aware of the argument made here:
<a href="https://stackoverflow.com/questions/8368547/how-to-find-the-longest-heaviest-trail-in-an-undirected-weighted-graph">https://stackoverflow.com/questions/8368547/how-to-find-the-longest-heaviest-trail-in-an-undirected-weighted-graph</a>
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.)</p>

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

CC BY-SA 3.0
2014-01-22T12:39:44.203Z
This is not the exact same problem, but take a look at the Minimum Euilerian Extension problem which is quite similar.
R B
CC BY-SA 3.0
2014-01-22T13:56:16.507Z
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.
Marzio De Biasi
CC BY-SA 3.0
2014-01-22T13:59:12.017Z
It seems that it asks for the minimum number of edges whose deletion makes the graph has an Eulerian path. Possibly it can be solved similarly as the Minimum Eulianian Extension problem (by transforming to a, or a series of, matching problem)
Bangye
CC BY-SA 3.0
2014-01-22T14:02:57.373Z
@Bangye: but it is enough to ask if  G=(V,E) has a long trail of length |V| (or in other words if  |E|-|V| edges can be deleted and still have an eulerian path) and the condition on cubic graphs can be satisfied if and only if it has an Hamiltonian cycle ... I'm thinking of it ...
Marzio De Biasi
CC BY-SA 3.0
2014-01-22T14:09:04.147Z
@Marzio: Some misunderstanding! A trail is a walk in which the nodes can be repeated but no edges are repeated.
Bangye
CC BY-SA 3.0
2014-01-22T14:11:34.050Z
@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)
Marzio De Biasi
CC BY-SA 3.0
2014-01-22T14:20:44.600Z
@Marzio: Ok I got what you means. For cubic graphs, there is a trail of length |V|-1 iff there is a path of length |V|-1. Maybe edge-deletion to Eulerian cannot be solved similarly to Eulerian Extension.
Bangye
CC BY-SA 3.0
2014-01-22T14:34:18.853Z
The longest path in a line graph reduces to this problem, no?  And if I am not wrong, the Hamiltonian path in a line graph is NP-complete, which reduces to the longest path in a line graph.
Lamine
CC BY-SA 3.0
2014-01-22T15:23:31.423Z
@Lamine: No. Consider a star $K_{1,k}$ for example. Its line graph $L(K_{1,k})$ is a complete graph $K_{k}$, and thus has Hamiltonian paths. However, in $K_{1,k}$, any edge-simple path has length at most 2.
Yota Otachi
CC BY-SA 3.0
2014-01-22T15:46:15.267Z
@○Yota: I know that "G is Hamiltonian" is not equivalent to "L(G) is Hamiltonian". However, I seem to remember that the Hamiltonicity of a line graph is also $NP$-complete. I will look for the paper (It dates back to the 80's).
Lamine
CC BY-SA 3.0
2014-01-22T15:54:38.153Z
Here is the reference: A.A. Bertossi, The edge hamiltonian path problem is NP-complete, Information Process-
ing Letters, 13 (1981) 157-159.
Lamine
CC BY-SA 3.0
2014-01-23T02:07:54.573Z
@Lamine: Now I guess I missed your point... What would be your reduction? I wanted to say: it is not true that "$G$ has an edge-simple path of length $\ell$" iff "$L(G)$ has a vertex simple path of length $\ell$".
Yota Otachi
CC BY-SA 3.0
2014-01-23T09:35:53.657Z
The reduction would be "L(G) has a vertex-simple path of length $K$" iff "G has a trail of length $f(k)$". But you're right, my reduction is wrong. A vertex simple path in a line graph corresponds to a walk in the corresponding graph, not necessarily to a trail. (What is the cstheory stack exchange policy concerning wrong comments? Should I delete them?)
Lamine
CC BY-SA 3.0
2014-01-23T11:37:04.823Z
@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.
Yota Otachi
<graph-theory><graph-algorithms><hamiltonian-paths>
Is the longest trail problem easier than the longest path problem?
Jasper
# Is the longest trail problem easier than the longest path problem?

(Asked by: username_0 on 2014-01-22)

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?

**Tags:** graph-theory, graph-algorithms, hamiltonian-paths

> **Comments:**
> **username_1**: This is not the exact same problem, but take a look at the Minimum Euilerian Extension problem which is quite similar.  
> **username_2**: 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.  
> **username_3**: It seems that it asks for the minimum number of edges whose deletion makes the graph has an Eulerian path. Possibly it can be solved similarly as the Minimum Eulianian Extension problem (by transforming to a, or a series of, matching problem)  
> **username_2**: @username_3: but it is enough to ask if  G=(V,E) has a long trail of length |V| (or in other words if  |E|-|V| edges can be deleted and still have an eulerian path) and the condition on cubic graphs can be satisfied if and only if it has an Hamiltonian cycle ... I'm thinking of it ...  
> **username_3**: @Marzio: Some misunderstanding! A trail is a walk in which the nodes can be repeated but no edges are repeated.  
> **username_2**: @username_3: 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)  
> **username_3**: @Marzio: Ok I got what you means. For cubic graphs, there is a trail of length |V|-1 iff there is a path of length |V|-1. Maybe edge-deletion to Eulerian cannot be solved similarly to Eulerian Extension.  
> **username_4**: The longest path in a line graph reduces to this problem, no?  And if I am not wrong, the Hamiltonian path in a line graph is NP-complete, which reduces to the longest path in a line graph.  
> **username_5**: @username_4: No. Consider a star $K_{1,k}$ for example. Its line graph $L(K_{1,k})$ is a complete graph $K_{k}$, and thus has Hamiltonian paths. However, in $K_{1,k}$, any edge-simple path has length at most 2.  
> **username_4**: @○Yota: I know that "G is Hamiltonian" is not equivalent to "L(G) is Hamiltonian". However, I seem to remember that the Hamiltonicity of a line graph is also $NP$-complete. I will look for the paper (It dates back to the 80's).  
> **username_4**: Here is the reference: A.A. Bertossi, The edge hamiltonian path problem is NP-complete, Information Process- ing Letters, 13 (1981) 157-159.  
> **username_5**: @username_4: Now I guess I missed your point... What would be your reduction? I wanted to say: it is not true that "$G$ has an edge-simple path of length $\ell$" iff "$L(G)$ has a vertex simple path of length $\ell$".  
> **username_4**: The reduction would be "L(G) has a vertex-simple path of length $K$" iff "G has a trail of length $f(k)$". But you're right, my reduction is wrong. A vertex simple path in a line graph corresponds to a walk in the corresponding graph, not necessarily to a trail. (What is the cstheory stack exchange policy concerning wrong comments? Should I delete them?)  
> **username_5**: @username_4: 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.  

---

## 1 answers

### Answer by username_2 on 2014-01-22. Score: 21 | Accepted answer

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

> **Comments:**
> **username_0**: 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.  
> **username_2**: 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).  

---

