I'm trying to prove that the Subgraph isomorphism problem is NPC using the Hamiltonian Cycle problem.

Unfortunately I feel (or don't understand) that the solution is "empty" and doesn't explain the Hamiltonian Cycle - Subgraph Isomorphic connection, @Luke Mathieson says that "Hamiltonian Cycle to Subgraph Isomorphism is really just rephrasing what it means for a graph to have a Hamiltonian cycle" - but I don't get it.

How does one transforms from Hamiltonian Cycle to Subgraph Isomorphism?

I read Reducing from Hamiltonian Cycle to Subgraph Isomorphism and https://en.wikipedia.org/wiki/Subgraph_isomorphism_problem and couldn't understand how should a proper reduction look like, how to build one that proves the subgraph problem?

Your help in simplifying the problem(s) will be very appreciated.

  • $\begingroup$ You name the duplicate yourself -- what specifically did you not understand? $\endgroup$ – Raphael Feb 6 '16 at 17:04

Reduction $HC \leq SubgraphIsomorphism$ is done as $G \rightarrow \langle G, C_n \rangle$ where $n$ is the number of vertices in $G$, and $C_n$ is the cycle graph with $n$ vertices. This effectively means that $G$ has a subgraph $C_n$ if and only if $G$ has a Hamiltonian Circuit.

There are mainly three types of common reductions. $A \leq_L B$, $A \leq_P B$ and $A \leq_M B$ i.e. log-space reduction, polynomial-time reduction and turing reduction. If we don't specify, it usually means polynomial-time reduction which is also known as Karp reduction.

Let us take $A \leq_P B$. It means we can transform an input $x$ of problem $A$ to an input $f(x)$ of problem $B$ in polynomial-time such that (and this is important) $x$ is a yes-instance of $A$ if and only if $f(x)$ is a yes-instance of $B$. This effectively gives us a polynomial-time algorithm to check yes-instances of problem $A$ if there is a known polynomial-time algorithm to check yes-instances of problem $B$.

Now if $A$ is known to be a tough problem, like Hamiltonian Circuit problem, then $A \leq B$ will imply that $B$ is also a tough problem. That is, since $HC$ is NP-complete, SubgraphIsomorphism is also NP-complete (as we also know additionally that Subgraph Isomorphism is in NP, otherwise we would have only shown its NP-hardness).

| cite | improve this answer | |

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