[Solved]: The $\text{k-key}$ problem

Problem Detail: 

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?

Asked By : Ben Benli

Answered By : Xodarap

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?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2676

3.2K people like this

 Download Related Notes/Documents