5
$\begingroup$

I was trying to understand the Wikipedia proof for NP-completeness of subgraph isomorphism by reduction from the clique problem. It's really just one sentence:

Let $H$ be the complete graph $K_k$; then, the answer to the subgraph isomorphism problem for $G$ and $H$ is equal to the answer to the clique problem for $G$ and $k$.

In the subgraph isomorphism problem, $G$ and $H$ are not constrained in any way (e.g., $H$ is not constrained to complete graphs). Yet, in the proof, Wikipedia just states "let $H$ be the complete graph $K_k$". It's not defined what $K_k$ represents or why $H$ suddenly becomes constrained to a complete graph.

|cite|improve this question
$\endgroup$
  • $\begingroup$ From Wikipedia: $K_k$ denotes the complete graph on $k$ vertices. Some sources claim that the letter $K$ stands for the German word komplett, while other sources state that $K$ honors the contributions of Kazimierz Kuratowski to graph theory. $\endgroup$ – Mario Cervera Oct 12 '16 at 1:19
4
$\begingroup$

The decision version of the clique problem asks whether a given graph $G$ contains a complete graph with $k$ vertices as subgraph. The wikipedia article just explains why the decision version of the clique problem is a special case of the subgraph isomorphism problem. Namely if the graph $H$ is the complete graph with $k$ vertices, then the answer to this special subgraph isomorphism problem is just the answer to the decision version of the clique problem.

This shows that subgraph isomorphism is NP-hard, since the clique problem is NP-complete. But the subgraph isomorphism is obviously in NP, since it a given monomorphism from $H$ to $G$ can efficiently be checked to be a monomorphism. So we can conclude that subgraph isomorphism is NP-complete.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ Is H constrained to be a complete graph in the subgraph isomorphism problem? If it is not constrained, how is the proof still valid? $\endgroup$ – Atte Juvonen Oct 12 '16 at 0:21
  • 5
    $\begingroup$ @AtteJuvonen In the subgraph isomorphism problem, H can be any graph, which includes the case that H is a complete graph. The goal is to use the subgraph isomorphism problem to solve the clique problem (not the other way round, like you seem to assume). $\endgroup$ – Thomas Klimpel Oct 12 '16 at 0:28
0
$\begingroup$

You misunderstood the proof of NP-completeness of Subgraph Isomorphism (SI).

  1. We know that SI $\in$ NP because we can check its solution in polynomial time.
  2. Any instance of clique problem (which is NP-complete) can be reduced in polynomial time to some instance of SI. This concludes that any problem in NP can be reduced to some instance of SI.

If you read the definition of NP-completeness, you will find out that its requirement satisfied by word any. The word some doesn't contradict it in any way.

|cite|improve this answer
$\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.