# Prove NP-completeness of deciding whether there is an edge-tour of at most a given length

We are given a graph G, integer b < |E|, and subset F in E. The problem is to detect whether there is a cycle in the graph with length at most b and includes each edge in F. Prove that this is NP Complete.

I'm thinking of reducing from Hamiltonian Path, but still can't think of the appropriate transformation function.

• What have you tried, and why specifically did it fail? Have you checked out reference questions? – Raphael Apr 21 '13 at 15:44

It is a standard variation of the Travelling Salesman Problem.

To force an edge to be a part of the answer, break it in half and insert a new vertex.

Update A reduction in the other direction consists of "breaking all vertices in two".

More precisely, given a directed graph $G$, form another graph $G'$. For each vertex $v$ in $G$, create a pair of vertices $v_i$, $v_o$ in $G'$. For each edge $(uv)$ in $G$, create an edge $(u_ov_i)$ in $G'$. Also, for each $v_i$, $v_o$ add an edge ($v_iv_o)$, and let it belong to $F$. Now every cycle in $G'$ that contains all edges in $F$ also contains all vertices, and corresponds to a Hamiltonian cycle in $G$.

• To show that the problem is NP-hard, you need the transformation in the opposite direction. – Daniel Apr 21 '13 at 14:34
• @Daniel: The other direction is trivial. If you can solve this, you can find Hamiltonian cycles and solve variants of TSP. Just set $F=\emptyset$. – n. 'pronouns' m. Apr 21 '13 at 14:45
• The other direction is not trivial to me, because the problem here asks for any cycle up to a given length. Given a machine to do this, can you really solve Hamiltonian cycle or will it just return a small cycle that does not include all vertices? – mcdowella Apr 21 '13 at 15:09
• @mcdowella: Hm, I think I have misread the problem. I was sure it does include the requirement to visit each vertex exactly once. Nevertheless it is still equivalent to the Hamiltonian cycle problem, though in a less obvious way. I shall update the answer. – n. 'pronouns' m. Apr 21 '13 at 15:22