# The $\text{k-key}$ problem

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?

• 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? Jul 10, 2012 at 20:47
• @Ben Benli: Yep! Jul 10, 2012 at 21:09
• 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? Jul 10, 2012 at 21:32
• @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. Jul 10, 2012 at 22:03
• @Xodarap Please consider updating your answer with the result of the discussion, maybe in spoiler tags if you prefer it that way.
– Raphael
Jul 22, 2012 at 9:52