“子图同构问题 NP-Complete 证明”

子图同构（Subgraph isomorphism problem）问题的描述如下。给定两个图 和 ，判断 是否与 的一个子图同构。首先假如我们得到了 ， 和对应的解（即 的子图 使得 与 同构），我们只需要遍历解中的点和每一个与这个点相连接的边，检查是否与 对应即可验证解的正确性。所以这个问题首先显然是一个 NP 问题。

为了证明这个问题同时也是一个 NP 难问题，我们将 分团问题 规约到 子图同构问题上来。具体地，假设我们现在有一个有解的分团问题 ，即 中存在 个点可以构成团（即这 个点相互连接，即构成一个 -完全图）。那么我们构造一个 为 -完全图，构造 。显然上述两个图的构造是可以在多项式时间内完成的。

考虑若有一个算法 $A_s$ 可以在多项式时间内解决子图同构问题的话，那么我们对于一个分团问题，我们只需要按照上述构造，在多项式时间内通过分团问题的 和 构造出 和 ，然后将 ， 拿给子图同构问题的算法 解，即可在多项式时间内得知 是否是 子图的一个同构，即 -完全图是否包含在 中，即在多项时间内解出了分团问题。

由于我们已知分团问题是 NP 完全的，所以上述的算法 不存在，所以子图同构问题为 NP 难问题。综上所述，子图同构问题是 NP 完全的。