Given an undirected graph, I define a structure called k-key as a path containin

Question

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?

Explanation / Answer

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?

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.