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?
1 Answer 1
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– Ben Benli2012年07月10日 20:47:23 +00:00Commented Jul 10, 2012 at 20:47
-
$\begingroup$ @Ben Benli: Yep! $\endgroup$Xodarap– Xodarap2012年07月10日 21:09:24 +00:00Commented Jul 10, 2012 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– Ben Benli2012年07月10日 21:32:19 +00:00Commented Jul 10, 2012 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– Xodarap2012年07月10日 22:03:31 +00:00Commented Jul 10, 2012 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– Raphael2012年07月22日 09:52:36 +00:00Commented Jul 22, 2012 at 9:52
Explore related questions
See similar questions with these tags.