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$
8
  • 2
    $\begingroup$ Try solving it for small values of $k$ first. $\endgroup$ Nov 25, 2017 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$ Nov 25, 2017 at 21:24
  • 1
    $\begingroup$ Actually, for $k=1,2$ there's nothing to do. The first interesting case is $k=3$. $\endgroup$ Nov 25, 2017 at 21:44
  • 1
    $\begingroup$ "Can I ...?" You can do whatever you want as long as you manage to prove that it works. $\endgroup$ Nov 25, 2017 at 22:15
  • 1
    $\begingroup$ Hint: A graph with 50 cliques of size $k$ contains a clique of size $k$. $\endgroup$ Apr 5, 2019 at 18:45

1 Answer 1

2
$\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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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