支配集问题是图论中的一个基本问题：给定一个图，寻找一个最小权重的顶点子集，使得每个顶点要么被选中，要么与选中的顶点相邻。在在线环境中，顶点按顺序到达，比较算法与具有完全输入知识的离线最优算法会导致极强的下界。例如，简单的星型图表明任何在线算法的竞争比率必须为 $\Omega(\Delta)$，其中 $\Delta$ 是图中任何顶点的最大度，这与选择所有顶点的简单策略相匹配。
我们研究增量支配集问题，其中最优算法受到与在线算法相同选择的约束。这为算法之间提供了一个有意义的比较基准。我们首次在此模型中针对顶点加权图和随机算法提出结果。对于增量支配集，我们提供了一个 $O(\Delta)$-竞争的确定性算法和一个 $O(\log^2\Delta)$-竞争的随机算法。
我们将这些结果扩展到连接支配集问题，使用线性规划的形式来通过局部约束捕捉连通性。当每个到达顶点的邻域事先已知时，确定性算法实现了与随机算法相似的多对数竞争比率。最后，我们建立了匹配的下界，表明我们的结果在常数因子上是最优的。
博主点评： 本文在增量支配集问题上的研究为图论领域提供了新的视角，尤其是在对比在线与离线算法时。这种新型的约束和结果展示了随机算法与确定性算法在复杂度上的微妙关系，为未来的研究提供了坚实的理论基础。通过对连接支配集问题的扩展，研究者们进一步推动了这一领域的发展。