0
$\begingroup$

I found many solution online on how to reduce Subgraph Isomorphism problem to Clique, but how do I prove that it is NP complete by reduction from independent set?

I'm struggling to figure out this proof through independent set. Any hints?

$\endgroup$

1 Answer 1

2
$\begingroup$

The idea is exactly the same: an undirected graph $G = (V, E)$ has an independant set of size $k$ if and only if the graph $(\{1,…,k\}, \emptyset)$ (the graph with $k$ vertices and no edge) is isomorphic to a subgraph of $G$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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