# Reduction of Hamiltonian cycle to Hamiltonian cycle & clique

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.

• Try solving it for small values of $k$ first. – Yuval Filmus Nov 25 '17 at 20:39
• @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? – plagueheart Nov 25 '17 at 21:24
• Actually, for $k=1,2$ there's nothing to do. The first interesting case is $k=3$. – Yuval Filmus Nov 25 '17 at 21:44
• @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. – plagueheart Nov 25 '17 at 22:01
• "Can I ...?" You can do whatever you want as long as you manage to prove that it works. – Yuval Filmus Nov 25 '17 at 22:15

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.