1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Try solving it for small values of $k$ first. $\endgroup$ – Yuval Filmus Nov 25 '17 at 20:39
  • $\begingroup$ @YuvalFilmus So for example--taking k=1 and seeing how I can insert a single point into G without disrupting or creating a Hamiltonian cycle? $\endgroup$ – plagueheart Nov 25 '17 at 21:24
  • $\begingroup$ Actually, for $k=1,2$ there's nothing to do. The first interesting case is $k=3$. $\endgroup$ – Yuval Filmus Nov 25 '17 at 21:44
  • $\begingroup$ @YuvalFilmus I think I may have something: Can I split a given vertex $z$ into two vertices with the clique between them, where both $z_1$ and $z_2$ share edges with vertices $z$ was adjacent to? If $z$ was in a cycle originally, I should be able to use the two cycle edges originally incident to z to enter & exit the $z_1$ -- clique -- $z_2$ structure; if there was no cycle, doing this won't create a new one because there was never a cycle for $z$ to be part of. $\endgroup$ – plagueheart Nov 25 '17 at 22:01
  • $\begingroup$ "Can I ...?" You can do whatever you want as long as you manage to prove that it works. $\endgroup$ – Yuval Filmus Nov 25 '17 at 22:15
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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