Given an undirected graph, I define a structure called k-key as a path containing $k$ vertices which are connected to a simple cycle which contains $k$ vertices as well.

Here's the k-key problem: given an undirected graph $G$ and a number $k$, decide whether $G$ contains k $k$-key.

I want to show that the k-key problem is a NP-complete.

I want to make a reduction from the 'Undirected Hamiltonian Cycle' problem in which the input is a graph, and the problem is to decide whether it contains a Hamiltonian path. I already know that this problem is NP-complete. The input for the reduction would be an undirected graph $G$ and the output is $G'$ graph and $k$. Can you please help me understand what manipulation I should do to the original graph in order to show this reduction? And why should it work?


You want to find a way of creating $G'$ from $G$ such that $G'$ has a $k$-key iff $G$ has a Hamiltonian path.

If a graph $G$ has $k$ vertices and a simple path of length $k$, then what can we conclude about it having a Hamiltonian path?

I'm guessing the intention is that the vertices in the path must be different from the vertices in the cycle (otherwise every ham cycle graph would contain a $k$-key and vice versa). So just think, suppose we knew that $G$ had a ham cycle starting from some vertex. Where would we tack on some vertices to create a $G'$ that had a $k$-key using $G$'s ham cycle?

  • $\begingroup$ Can you just travel on the ham cycle, count the vertices and add to some vertex a simple flat path of the number we counted vertices? $\endgroup$ – Ben Benli Jul 10 '12 at 20:47
  • $\begingroup$ @Ben Benli: Yep! $\endgroup$ – Xodarap Jul 10 '12 at 21:09
  • $\begingroup$ This structure we build is good for the two 'iff' directions?I mean If G is hamilton then G' is $k$-key, but for the other direction can I just say that by the way we built $G'$ then $G$ has an ham cycle? or should I do something to the structure? $\endgroup$ – Ben Benli Jul 10 '12 at 21:32
  • $\begingroup$ @Ben: basically what you're asking is: "If $G'$ is a key, is the cycle part of the key entirely inside $G$?" This is not too hard to verify. $\endgroup$ – Xodarap Jul 10 '12 at 22:03
  • $\begingroup$ @Xodarap Please consider updating your answer with the result of the discussion, maybe in spoiler tags if you prefer it that way. $\endgroup$ – Raphael Jul 22 '12 at 9:52

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.