# 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.

## migrated from stackoverflow.comApr 21 '13 at 14:19

This question came from our site for professional and enthusiast programmers.

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

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$.
• @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