求距离大于2的独立集问题归约为NPC问题的方法咨询

要证明该问题（下文称3-距离独立集问题）属于NPC，我们可以从经典的NPC问题——独立集问题出发，通过多项式时间归约完成证明。

1. 问题定义 #

• 独立集问题（IS）：给定图$H=(V_H, E_H)$和整数$k$，判断是否存在子集$S \subseteq V_H$，满足$|S| \geq k$，且$S$中任意两个节点在$H$中不相邻。
• 3-距离独立集问题（P）：给定图$G=(V, E)$和整数$k$，判断是否存在子集$V' \subseteq V$，满足$|V'| \geq k$，且$V'$中任意两个节点在$G$中的距离$\text{dist}(u, v) \geq 3$。

2. 多项式时间归约构造 #

对于任意独立集问题实例$(H, k)$，我们构造3-距离独立集问题的实例$(G, k)$：

• 节点集：$V = V_H \cup {v' \mid v \in V_H}$，即每个$H$中的节点$v$对应$G$中的两个节点：原节点$v$和复制节点$v'$。
• 边集：
  • 对每个$v \in V_H$，添加边$(v, v')$（原节点与自身复制节点相连）；
  • 对每条边$(u, v) \in E_H$，添加边$(u', v)$和$(v', u)$（复制节点与原节点相连，对应$H$中的邻接关系）。

显然，这个构造过程是多项式时间的，因为节点和边的数量都仅为原实例的线性倍数。

3. 等价性证明 #

我们需要证明：$H$存在大小为$k$的独立集 $\iff$ $G$存在大小为$k$的3-距离独立集。

正向推导（IS实例有解 ⇒ P实例有解） #

假设$S$是$H$中大小为$k$的独立集，取$V' = S$（即直接取$H$中独立集的原节点作为$G$的候选子集）。

• 对于任意$u, v \in V'$，由于$S$是独立集，$(u, v) \notin E_H$，因此$G$中不存在$u$与$v$的直接边；
• $u$的邻居仅有$u'$，$v$的邻居仅有$v'$。由于$(u, v) \notin E_H$，$G$中不存在$(u', v)$或$(v', u)$的边，因此$u$和$v$没有共同邻居；
• 综上，$\text{dist}_G(u, v) \geq 3$，$V'$满足P问题的条件。

反向推导（P实例有解 ⇒ IS实例有解） #

假设$V'$是$G$中大小为$k$的3-距离独立集：

• 由于$v$和$v'$在$G$中相邻（距离为1），$V'$中不可能同时包含$v$和$v'$，因此$V'$中的每个节点要么是原节点，要么是复制节点；
• 将$V'$中的所有复制节点$v'$替换为对应的原节点$v$，得到集合$S \subseteq V_H$，显然$|S| = k$；
• 假设$S$不是$H$的独立集，则存在$u, v \in S$使得$(u, v) \in E_H$。此时$G$中存在边$(u', v)$，那么$u$到$v$的路径为$u \to u' \to v$，距离为2，这与$V'$中任意两点距离≥3的条件矛盾；
• 因此$S$是$H$的独立集。

结论 #

由于独立集问题是NPC问题，且我们通过多项式时间归约将其转化为3-距离独立集问题，因此3-距离独立集问题属于NPC问题。

内容的提问来源于stack exchange，提问作者Ahmad Ali