1
$\begingroup$

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.

$\endgroup$

migrated from stackoverflow.com Apr 21 '13 at 14:19

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

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

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

$\endgroup$
  • $\begingroup$ To show that the problem is NP-hard, you need the transformation in the opposite direction. $\endgroup$ – Daniel Apr 21 '13 at 14:34
  • $\begingroup$ @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$. $\endgroup$ – n. 'pronouns' m. Apr 21 '13 at 14:45
  • $\begingroup$ 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? $\endgroup$ – mcdowella Apr 21 '13 at 15:09
  • $\begingroup$ @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. $\endgroup$ – n. 'pronouns' m. Apr 21 '13 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.