11.19

To prove NP-hardness we reduce the classic CLIQUE problem to the stated Maximum Common Subgraph (MCS) problem.

CLIQUE instance: a graph [math]G=(V,E)[/math] and an integer [math]k[/math].
Question: does [math]G[/math] contain a clique of size [math]k[/math]?

Reduction (polynomial-time)
1. Let [math]G_1:=G[/math].
2. Construct [math]G_2:=K_k[/math], the complete graph on exactly [math]k[/math] vertices.
3. Set the budget [math]b:=k[/math].

Correctness
• (Soundness) suppose the CLIQUE instance is YES, i.e. there exists [math]C\subseteq V[/math] with |C|=k and the subgraph [math]G[C][/math] is isomorphic to [math]K_k[/math]. Choose
   [math]S_1:=V\setminus C[/math] (delete every vertex not in the clique) and [math]S_2:=\varnothing[/math] (nothing to delete from [math]G_2[/math]).
   After deletion both graphs contain exactly [math]k=b[/math] vertices and are identical copies of [math]K_k[/math]; therefore MCS answers YES.
• (Completeness) conversely, assume the MCS instance built above is YES. Because [math]G_2[/math] has only [math]k[/math] vertices, the budget forces
   |V_2\setminus S_2|=k[/span]; hence no vertex of [math]G_2[/math] can be deleted and the resulting common graph must be [math]K_k[/math].
   The identical copy inside [math]G_1[/math] is induced by the vertex set [math]V_1\setminus S_1[/math]; thus those [math]k[/math] vertices form a clique in [math]G[/math]. Hence the original CLIQUE instance is YES.

Conclusion the transformation is polynomial and preserves YES/NO answers, so MCS is at least as hard as CLIQUE; therefore the decision version of the Maximum Common Subgraph problem is NP-hard.■

Back to Chapter 11