2
$\begingroup$

I am reading Subgraph isomorphism problem

I am having trouble understanding how they prove that the subgraph isomorphism problem is NP-Complete using the Hamiltonian cycles problem in the article.

Can someone help me explain what is happening in more laymen terms?

$\endgroup$
  • $\begingroup$ I edited the title to refer to subgraph isomorphism. The graph isomorphism problem is not the same thing and whether or not there is a reduction from Hamiltonian Cycle to Graph Isomorphism is one of the biggest open questions in complexity theory. $\endgroup$ – David Richerby Dec 12 '13 at 9:20
7
$\begingroup$

In $\mathrm{Subgraph\,\,Isomorphism}$, you're given two graphs $G$ and $H$, and the question is whether you can delete some vertices and edges from $G$ to get $H$ (i.e. $H$ is a subgraph of $G$). The reduction from $\mathrm{Hamiltonian\,\,Cycle}$ to $\mathrm{Subgraph\,\,Isomorphism}$ is really just rephrasing what it means for a graph to have a Hamiltonian cycle.

A Hamiltonian cycle in a graph is a cycle that includes every vertex, so if we ignore the other edges in the graph, we can think of the Hamiltonian cycle as a subgraph of the original graph with the properties that it contains all the vertices, only some of the edges, and those edges make a cycle. That is, a Hamiltonian cycle in an $n$-vertex is isomorphic to the graph $C_{n}$.

So if we start with $G$ and we can find a subgraph that's isomorphic to $C_{|V(G)|}$, $G$ must be Hamiltonian. This is the same as solving the $\mathrm{Subgraph\,\,Isomorphism}$ problem where $H=C_{|V(G)|}$.

$\endgroup$
  • $\begingroup$ In other words, any graph, G, with a Hamiltonian cycle will have an isomorphic subgraph equal to the edges used by the Hamiltonian cycle and all vertices in G? $\endgroup$ – DanGoodrick Apr 5 at 13:02
  • $\begingroup$ @DanGoodrick yep! $\endgroup$ – Luke Mathieson Apr 5 at 22:03

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.