题目

image.png

知识点

NP-complete、独立集问题

解题思路

要证明一个问题是NP-完全问题，可以将已知的某个NP-完全问题归约到该问题。比如对于本题，我们可以用独立集的问题（一个已知的NP-完全问题）来归约得出公共子图问题也是NP-完全问题。首先，假设我们要求G1=（V，E）中大小为b的独立集的问题（NP-完全问题），令G2=（V， ∅），因为G2没有边，即G2中的各个点都是相互独立的，所以G1和G2存在节点个数为b的公共子图当且仅当G1存在着大小为b的独立集。故而要最大公共子图问题可以由最大独立集问题归约得来，即也是NP-完全的。

image.png