2
$\begingroup$

Just want to verify that I have the right idea here with this hamiltonian cycle question.

$HC$ = $\{\langle G \rangle$ | $G=(V,E)$ is an undirected graph such that there is a simple cycle (no vertex repeats) C in the graph that contains all vertices $\}$

$2HC$ = $\{\langle G \rangle$ | $G=(V,E)$ is an undirected graph such that there are two simple cycles $C_1$ and $C_2$ such that atleast one of the cycles contains every vertex $\}$

Using the fact that $HC$ is NP-complete, we wish to prove that $2HC$ is NP-complete.

a) Prove that $2HC \in NP$

My actual written proof is a bit too lengthy so I will just summarize the idea. We know $HC$ is NP-complete and therefore has a polynomial time verifier $V$ that can check for a cycle including all vertices. We can use this verifier to verify $2HC$ but we know that $2HC$ can contain a cycle that does not include all vertices. So we need a second verifier $V'$ that needs to only check for cycles but not ones that include all vertices. There are 3 cases to consider:

  • If $V$ accepts both cycles in $2HC$, accept and no need to run $V'$
  • If $V$ accepts only $C_1$, run $V'$ on $C_2$ to check if its a cycle, if $V'$ accepts, accept.
  • If $V$ accepts only $C_2$, run $V'$ on $C_1$ to check if its a cycle, if $V'$ accepts, accept.

Thus $2HC$ can be verified in polynomial time since both $V$ and $V'$ run in polynomial time so $2HC \in NP$.

b) Prove that $2HC$ is NP-hard by showing that $HC \le_p 2HC$

We already know that $HC$ contains a cycle with all vertices. To reduce $HC$ to $2HC$ we need to introduce a new vertex $v'$ that will connect to 2 vertices $u,w \in G$ such that $u \neq w$. Notice that this will create a second cycle. Since we can easily create a function that adds the new vertex along with the additional 2 edges, the function takes polynomial time and so we have $HC \le_p 2HC$.

Since $2HC \in NP$ and $HC \le_p 2HC$, we can conclude that $2HC$ is NP-Complete.

$\endgroup$
3
$\begingroup$

Your proof of (a) is much more complex than it needs to be. Instead of reducing to a known problem you can just say it directly: 2HC is in NP because it is solved by the nondeterministic machine that guesses two cycles and then checks that they are in fact cycles and contain all vertices between them, and all this is easy to do in polynomial time.

For (b) you have the right general idea, but the execution seems to be slightly flawed. Introducing just one new vertex with edges to existing vertices will not guarantee that the new vertex is the only vertex that benefits from the new cycle. For example, consider the graph

1---3---4---5
 \ /
  2

If you add a new vertex connected to 4 and 5, the new graph will be in 2HC even though the original graph is not Hamiltonian.

Instead, just introduce an entire new cycle -- three new vertices with three new edges between them, and not connected to the existing graph.

$\endgroup$
  • $\begingroup$ Thanks for the tips however I have one concern for part b. According to the definition of $HC$, the cycle must include all vertices but in your example 4,5 are not in the cycle 1,3,2. So if all vertices are in the cycle, adding 1 vertex connecting to 2 different vertices already in the cycle will infact create a new cycle. Please correct me if im wrong. $\endgroup$ – 1337holiday Apr 4 '14 at 20:10
  • $\begingroup$ @1337holiday: Yes, that's the point. The original graph is not in HC, but the rewritten one is in 2HC -- so your reduction will not give the right answer. $\endgroup$ – Henning Makholm Apr 4 '14 at 20:36
  • $\begingroup$ ACtually I'm still a slight bit confused at the moment. Are we transforming $HC$ into $2HC$ or $2HC$ into $HC$ because all the examples I am seeing for the reductions are doing it the latter way. $\endgroup$ – 1337holiday Apr 4 '14 at 23:48
  • $\begingroup$ @1337holiday: In order to prove that 2HC is NP-hard, you reduce from the known NP-hard problem HC to the new problem 2HC -- that is, for every input to HC you need to produce (in polynomial time) an input to 2HC that has the same answer. That is, you turn a HC problem into a 2HC problem, but this can also be viewed as a way to turn a 2HC solver into a HC solver. The latter is what you want -- we believe that fast HC solvers probably don't exist, so by arguing that an fast 2HC solver can be turned into an fast HC solver, we conclude that 2HC cannot be solved quickly either. $\endgroup$ – Henning Makholm Apr 5 '14 at 0:43
  • $\begingroup$ Right, but I don't get your example that you provided because if we are transforming an $HC$ problem into a $2HC$ as you stated, how can your example have 4,5? If a problem is already $HC$ then shouldn't 4,5 be part of the cycle which is what makes it a Hamiltonian cycle? $\endgroup$ – 1337holiday Apr 5 '14 at 0:56

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.