The Dominating Set problem is a fundamental issue in graph theory: given a graph, find a minimum-weight subset of vertices such that every vertex is either selected or adjacent to a selected vertex. In online settings where vertices arrive sequentially, comparing algorithms against an offline optimum with full knowledge of the input leads to extremely strong lower bounds. For instance, a simple star graph shows that any online algorithm must have a competitive ratio of $\Omega(\Delta)$, where $\Delta$ is the largest degree of any vertex in the graph, matching the trivial strategy of selecting all vertices.
We study the incremental dominating set problem, where the optimal algorithm is constrained to the same choices available to online algorithms. This introduces a benchmark that enables a meaningful comparison between algorithms. We present the first results for vertex-weighted graphs and randomized algorithms in this model. For incremental dominating set, we provide an $O(\Delta)$-competitive deterministic algorithm and an $O(\log^2\Delta)$-competitive randomized algorithm.
We extend these results to the Connected Dominating Set problem using a linear-programming formulation that captures connectivity through local constraints. When the neighborhood of each arriving vertex is known in advance, deterministic algorithms achieve similar polylogarithmic competitive ratios as their randomized counterparts. Finally, we establish matching lower bounds, showing that our results are optimal up to constant factors.
Blogger's Review: This paper offers a fresh perspective on the incremental dominating set problem, particularly in contrasting online and offline algorithms. The new constraints and results highlight the nuanced relationship between randomized and deterministic algorithms in terms of complexity, laying a solid theoretical foundation for future research. The extension to the connected dominating set problem further advances the field significantly.