I am trying to determine, whether the problem of a trail of given length in a graph is a NPC problem.
We have a graph $G = (V, E)$ and $k \in N^+$. Does this graph contain a trail of length at least $k$?
This problem is obviously NP: if we have a solution, we can check it in polynomial time (just check that given trail contains $k$ edges and these edges do not repeat - this can be done even in linear time).
This may be similar to finding biggest Eulerian subgraph in a graph which is NP-hard problem but I think that this is easier since we need a trail of length at least $k$, not the biggest one.
So I am looking for a NPC problem to reduce my problem to. Some adepts would be Hamiltonian circuit problem or Vertex coverage but I am not sure how to begin with the reduction...
I am not looking for a complete solution to this problem, just a hint what to begin with. Thanks for any tips!
You can use the fact that finding out if a cubic (ie 3-regular) graph has an Hamiltonian cycle is NP-complete. I learned this from graphclasses.org
What's nice about trails in cubic graphs is that for a given vertex $x$, you can use up one edge to enter $x$, another to exit, and if somehow you use up the remaining edge, then your trail is over. Knowing this you should be able to get necessary and sufficient conditions that relate the existence of a Hamiltonian cycle and the existence of a trail of length $k$, for some specific $k$.