5
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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?

Improve this answer
$\endgroup$
5
  • $\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
    Commented Jul 10, 2012 at 20:47
  • $\begingroup$ @Ben Benli: Yep! $\endgroup$
    – Xodarap
    Commented 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
    Commented 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
    Commented 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
    Commented Jul 22, 2012 at 9:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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