Reduction of Hamiltonian cycle to Hamiltonian cycle & clique

Question

I've been given a homework problem to prove that determining whether a graph G has both a Hamilton cycle and a clique of size k is NP-complete.

Based on this question, I know an "easy" reduction exists from Hamiltonian path to Hamiltonian path & clique (or someone has said it exists), and I assume that the same is true for reducing Hamiltonian cycle to Hamiltonian cycle & clique.

My thought is to somehow insert a clique of size k into G such that it's in the original cycle. (If I can make it lie in the path of the original cycle, it shouldn't disrupt the cycle, as all cliques have a Hamiltonian path through them.) But there are two problems with this approach:

1. I'm not sure how to insert a clique in such a way it can't create or destroy a cycle. I've tried:

   • Inserting the clique on an arbitrary edge of the graph (can result in a G' without a Hamiltonian cycle)
   • Adding k-2 vertices and creating a clique between them and two adjacent vertices in G (can result in G' without a Hamiltonian cycle)
   • Inserting the clique between input & output nodes connected to two different vertices on the original graph (can result in G' with a Hamiltonian cycle where G did not have one, if the points are arbitrary, or G' without a Hamiltonian cycle if inserted across adjacent vertices)

2. More generally--if I can find a way to insert a clique while preserving G's original Hamiltonian cycle--does this actually satisfy the iff requirement of the reduction? I don't feel like it does, because the existence of the clique in G' is in no way contingent on the existence of the Hamiltonian cycle in G.

Could someone give me a push in the right direction on this? I'm totally stumped on another way to approach it.

Answer 1

For NP completeness, two things must be demonstrated.

1. That a solution to the problem can be verified in polynomial time (usually easy).

2. That the input to another NP Complete problem can be formatted as an input to the potentially NP complete problem (also that a solution from the potential NP Complete problem can be turned into a solution to the NP complete problem) all in polynomial time.

It looks like you are trying to go the wrong direction with your question. You are asking about inserting a Clique into a graph, but you only need to concern yourself with a graph that would be sent to a HP solver and modify the inputs so they are appropriate for a HP+Clique solver. The HP part of the candidate problem doesn't require any modification - it just takes an undirected graph G(V,E). A clique takes an undirected graph G(V,E) and a goal, k. So you need to define a k that is in $G_{HP}$. what if you set k=1?. This way, the only graphs that your solver will fail to find a solution for are those that don't have a HP since every node is a clique with itself. This takes O(1) to define k=1.

Now, you just need to modify the output of the HP+Clique so it is the same as the output for the HP problem. e.g. If the candidate problem produces a solution, you would only return the path part and drop the clique part. If a solution is not found, you return NO.