求图的最小支配集算法咨询：基于布尔矩阵表示的图

问题描述 #

给定以布尔矩阵表示的无向图（无自环，graph[i,j] = true 表示顶点i与j相连），需要找到最小顶点集合，使得图中每个顶点要么属于该集合，要么是集合内某顶点的邻居（即求解最小支配集问题）。

示例1 #

输入：

bool[,] dungeons2 = {{F, F, T, F, F},    
                  {F, F, T, F, F},    
                  {T, T, F, T, T},     
                  {F, F, T, F, F},   
                  {F, F, T, F, F}}; 

输出：[2]

示例2 #

输入：

bool[,] dungeons1 = 
{{F, T, F, F, F, F ,F},
 {T, F, T, F, F, T ,F}, 
 {F, T, F, T, F, T,F }, 
 {F, F, T, F, T, F ,T}, 
 {F , F, F, T, F, F,T }, 
 {F, T, T, F, F, F,F }, 
 {F, F ,F, T, T, F,F}};

输出：[1,3]

已尝试方法及困境 #

• 寻找割点集合：无法保证得到最小支配集
• 贪心策略（每次移除邻居最多的顶点及其所有邻居）：无法保证最优解

一、精确算法（保证最优） #

1. 回溯+剪枝 #

从空集开始，逐个尝试添加顶点，跟踪已支配的顶点集合。每一步可做剪枝优化：

• 若当前已选顶点数≥已知最小支配集大小，直接放弃该分支
• 优先选择能覆盖更多未支配顶点的顶点，减少无效分支

2. 分支定界算法 #

在回溯基础上，为每个分支计算下界（剩余未支配顶点至少需要的覆盖顶点数，可通过贪心估算：每次选覆盖最多未支配顶点的顶点，统计次数作为下界）。若当前分支已选顶点数+下界≥已知最优解，立即剪枝。

3. 整数线性规划（ILP） #

将问题转化为线性规划模型：

• 定义变量 x_i：x_i=1 表示顶点i在支配集中，x_i=0 则不在
• 约束条件：每个顶点i要么被选中（x_i=1），要么至少有一个邻居j被选中（Σx_j ≥1，j为i的邻居）
• 目标函数：最小化 Σx_i
  使用ILP求解器（如CPLEX、Gurobi、开源SCIP）可直接得到最优解，适合规模较小的图。

二、特殊图的高效算法 #

若图为树结构，可通过动态规划（DP）线性时间求解：
对每个节点u，维护三种状态：

• dp[u][0]：u不在支配集，且被父节点覆盖的最小支配集大小
• dp[u][1]：u在支配集的最小支配集大小
• dp[u][2]：u不在支配集，且被至少一个子节点覆盖的最小支配集大小
  通过后序遍历计算每个节点的状态值，根节点的最小状态值即为答案。

三、改进型启发式算法（近似最优，适用于大图） #

若图规模较大，精确算法效率不足，可采用以下启发式方法提升近似效果：

• 加权贪心：计算每个顶点的"覆盖效率"（覆盖的未支配顶点数），每次选效率最高的顶点，直至所有顶点被覆盖
• 局部搜索：先构造初始支配集（如贪心结果），尝试替换其中顶点，看能否缩小集合规模（比如移除一个顶点，再找最少的顶点填补其覆盖区域）
• 遗传算法：将支配集编码为二进制串，通过选择、交叉、变异操作迭代优化，得到近似最小集合

内容的提问来源于stack exchange，提问作者Jabel Resendiz