很不幸，这是NP难问题，所以可能没有多项式时间算法来解决它。以下是从NP难问题独立集中的简化，其中我们给定一个图G =（V，E）（其中n = | V |和m = | E |）和一个整数k，任务是确定是否可能找到一组k个或更多顶点，使得集合中没有两个顶点通过边连接：
- 对于G中的每个顶点v_i，在H中创建一个红色顶点r_i。
- 对于G中的每条边(v_i, v_j)，在H中创建以下内容：
- 一个黑色顶点b_ij，
- n+1个红色顶点t_ijk（1<=k<=n+1），
- n个黑色顶点u_ijk（1<=k<=n），
- n条边(t_ijk, u_ijk)（1<=k<=n），
- n条边(t_ijk, u_ij{k-1})（2<=k<=n+1），
- 三条边(r_i, b_ij), (r_j, b_ij)和(t_ij1, b_ij)。
- 对于每对顶点v_i、v_j，创建以下内容：
- 一个黑色顶点c_ij，
- 两条边(r_i, c_ij)和(r_j, c_ij)。
- 将阈值设置为m(n+1)+k。
将所有r_i的集合称为R，所有b_ij的集合称为B，所有c_ij的集合称为C，所有t_ij的集合称为T，所有u_ij的集合称为U。
这里的一般思路是强制每个黑色顶点b_ij选择最多两个红色端点r_i和r_j中的一个。我们通过给每个b_ij顶点3条出边来实现这一点，其中一条（指向t_ij1）是“必须拥有”的——也就是说，在任何不选择t_ij1顶点的解决方案中都可以通过选择它以及它连接的n个其他红色顶点（通过在t_ijk和u_ijk之间交替的“摆动路径”连接）来改进，如果需要，消除r_i或r_j以恢复没有3个或更多邻居的黑色顶点的性质，然后通过必要时从C中选择顶点来最终恢复连通性。（c_ij顶点是“连接器”：它们存在仅为了确保我们包含的R的任何子集可以成为单个连通组件。）
假设G中存在大小为k的IS。我们将展示在H中至少有m（n + 1）+ k个红节点的连接诱导子图X，其中每个黑色顶点在X中最多有2个邻居。
首先，在X中包括与IS中顶点对应的R中的k个顶点（根据假设，这样的集合必须存在）。因为这些顶点形成一个IS，所以B中的任何顶点都不与它们中的超过1个相邻，因此我们可以安全地将每个顶点b_ij及其开始于t_ij1的长度为2n + 1的“摆动路径”添加到X中。每个这样的摆动路径都包含n + 1个红色顶点，并且有m个这样的路径（对于G中的每条边都有一个），因此现在X中有m（n + 1）+ k个红色顶点。最后，为确保X是连通的，请添加每个c_ij顶点，使得r_i和r_j已经在X中：请注意，这不会改变X中红色顶点的总数。
现在假设在H中存在至少有m（n + 1）+ k个红节点的连接诱导子图X，其中每个黑色顶点在X中最多有2个邻居。我们将展示G中存在大小为k的IS。
H 中唯一的红色顶点是 R 和 T 中的顶点。R 中只有 n 个顶点，因此如果 X 不包含所有 m 条曲线路径，则其最多只能有 (m-1)(n+1)+n = m(n+1)-1 个红色顶点，这与假设它至少有 m(n+1)+k 个红色顶点相矛盾。因此 X 必须包含所有 m 条曲线路径。这使得 X 中还剩下 k 个其他的红色顶点，它们必须来自 R。这些顶点中没有两个顶点可以相邻于 B 中的同一个顶点，否则该 B-顶点将与 3 个顶点相邻：因此，这些 k 个顶点对应于 G 中的 IS。
由于 IS 的 YES 实例意味着您问题的构造实例也是 YES 实例，反之亦然，所以问题的解决方案与 IS 实例的解决方案完全相对应；并且由于构造显然是多项式时间的，因此这证明了您的问题是 NP-hard。
