最小支配子图问题：带指定顶点集约束的连通子图求解

给定图 (G(V,E))（由顶点集 (V) 和边集 (E) 定义），已知顶点子集 (W \subseteq V)，需找出 (G) 的一个连通子图 (G'(V',E'))，满足以下条件：

• i) 对任意顶点 (p \in V)，要么 (p \in V')，要么存在 (p' \in V') 与 (p) 相邻；
• ii) (W) 中所有顶点都必须包含在 (V') 内；
• iii) 在满足前两个条件的前提下，让 (V') 的规模尽可能小。

这个问题属于带约束的最小连通支配集（Constrained Minimum Connected Dominating Set, CMCDS），是NP-hard问题（除非P=NP，否则不存在多项式时间精确解法），分两种场景给出可行方案：

小规模图（求精确解） #

针对顶点数较少的图，可通过以下方式求解：

• 回溯/分支定界法：从包含 (W) 的初始连通顶点集出发（若 (W) 不连通，先补充顶点使其连通），尝试移除非 (W) 顶点，验证移除后是否仍满足连通性与支配集条件，递归迭代直到无法再缩减规模，得到最小 (V')。
• 整数线性规划（ILP）建模：
  1. 为每个顶点 (v \in V) 定义0-1变量 (x_v)，(x_v=1) 代表 (v \in V')；
  2. 约束条件：
     • 对所有 (w \in W)，(x_w = 1)；
     • 对所有 (p \in V)，(x_p + \sum_{u \in N(p)} x_u \geq 1)（(N(p)) 是 (p) 的邻域顶点集）；
     • 添加连通性约束（比如用流/割约束），确保所有 (x_v=1) 的顶点构成连通子图；
  3. 目标函数：最小化 (\sum_{v \in V} x_v)，借助ILP求解器得到精确解。

大规模图（求近似解） #

针对顶点数较多的图，采用近似或启发式算法：

• 两步法：
  1. 先构造包含 (W) 的近似最小支配集：从 (W) 出发，贪心选择能覆盖最多未被支配顶点的顶点加入集合；
  2. 若该支配集不连通，用最短路径树/最小生成树思路，补充最少顶点使其连通。
• 启发式算法：用模拟退火、遗传算法等，迭代优化初始连通支配集，逐步缩减顶点数量，同时保持约束条件成立。

• (W) 中的顶点是强制保留的，绝对不能从 (V') 中移除；
• 支配集条件要求原图所有顶点要么在 (V') 内，要么被 (V') 顶点覆盖；
• (V') 必须是连通的，不能拆分成多个孤立顶点子集。

内容的提问来源于stack exchange，提问作者Sword fish