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$

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .