Question

Show that the following problem is NP-complete.

MAXIMUM COMMON SUBGRAPHInput: Two graphs ${\mathbf{G}}_{\mathbf{1}}\mathbf{=}\left(V_1,E_1\right)$and ${\mathbf{G}}_{\mathbf{2}}\mathbf{=}\left(V_2,E_2\right)$; a budget $\mathbf{b}$.Output: Two set of nodes ${{\mathbf{V}}_{\mathbf{1}}}^{\mathbf{\text{'}}}\mathbf{\subseteq }{\mathbf{V}}_{\mathbf{1}}$and ${{\mathbf{V}}_{\mathbf{2}}}^{\mathbf{\text{'}}}\mathbf{\subseteq }{\mathbf{V}}_{\mathbf{2}}$whose deletion leaves at least$\mathbf{b}$ nodes in each graph, and makes the two graphs identical.

Short answer

The MAXIMUM COMMON SUBGRAPH is NP-complete.

Step-by-step solution

Explain NP-Complete

A problem that has no significant optimal solution is denoted as NP-hard. For such problems, the significant solutions can be found is called NP-Complete.

Show that the given problem is NP-Complete

Consider that the maximum independent set problem is reduced to the maximum common subgraph problem.

Consider the unique graph$\mathrm{G}\left(\mathrm{V},\mathrm{E}\right)$ of size $d$. Let,$G_1=G\left(V,E\right)$ and$G_2=\left(V,\varphi \right)$ have the same vertex set as$G$ but the edge set is empty.

Each vertex is independent of each other, so$G_1$ and$G_2$ have a subgraph in common in size $d$. The graphs are identical to each other if the vertices are deleted.

Therefore, the set of nodes ${V_1}^{\text{'}}\subseteq V_1$and${V_2}^{\text{'}}\subseteq V_2$ deletion leaves at nodes makes the two graphs identical is proved and it is NP-complete.