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-graphHowever, 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?
Is the longest trail problem easier than the longest path problem?
graph theory;graph algorithms;hamiltonian paths
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