Abstract
This paper investigates the Online Dominating Set problem under the vertex-arrival model. By introducing the "Optimal Incremental" ($OPT^{INC}$) benchmark alongside the traditional "Optimal Offline" ($OPT^{OFF}$), the authors isolate the performance penalties caused by the lack of future knowledge versus the requirement of maintaining a valid solution at every step. The study provides tight competitive ratios for various graph classes, including trees, bipartite, planar, and bounded-degree graphs, revealing that the "incremental tax" is often the primary bottleneck in online performance.
The Online Vertex-Arrival Model
In the Dominating Set (DS) problem, the goal is to identify the smallest subset of vertices $D$ such that every vertex in the graph is either in $D$ or adjacent to a vertex in $D$. This problem is a cornerstone of network routing and facility location. This research explores the problem through the online vertex-arrival model, where:
- Vertices arrive sequentially.
- Upon arrival, a vertex reveals all edges to previously arrived vertices.
- The algorithm must decide immediately whether to add vertices to the dominating set $D$.
- Decisions are irrevocable, and the algorithm must maintain a valid dominating set $D_i$ for the graph revealed up to step $i$.
The authors analyze four variants: Standard (DS), Connected (CDS), Total (TDS), and Independent (IDS).
Benchmarking the "Incremental Tax"
To evaluate performance, the authors employ competitive analysis with a novel distinction. They compare online algorithms against two benchmarks:
- $OPT^{OFF}$: The standard offline optimum that knows the entire graph in advance and selects the best set at the end.
- $OPT^{INC}$ (Optimal Incremental): An offline optimum that knows the entire graph but is constrained to be incremental—it must provide a valid solution for every prefix of the input.
This dual-benchmark approach allows researchers to determine if an algorithm's inefficiency stems from a lack of future knowledge or the inherent difficulty of maintaining a valid solution at every intermediate step.
Algorithmic Approaches
The paper introduces several key algorithms tailored for different graph structures:
- PARENT: Primarily for trees; when a new vertex is not dominated, the algorithm adds the vertex's "parent" (the node it connected to upon arrival) to the set.
- LOWPARENT: A generalized version for complex graphs that utilizes "layer numbers" (distance-based rankings) to prioritize which neighbors to include in the dominating set.
Key Results and Competitive Ratios
The researchers established tight or near-tight bounds for competitive ratios across various graph classes. A significant finding is that for many classes, the competitive ratio against $OPT^{INC}$ is nearly identical to that against $OPT^{OFF}$, suggesting that the requirement to be incremental is the dominant constraint.
As shown in the tables, Independent Dominating Set (IDS) is unique: for any graph and arrival order, there is only one unique incremental independent dominating set. Consequently, any online algorithm is 1-competitive against $OPT^{INC}$ for IDS, as it is effectively forced into the only valid path.
For Trees, the PARENT algorithm is remarkably efficient, achieving 1-competitiveness against $OPT^{INC}$ for Connected and Total DS. However, Planar Graphs proved surprisingly difficult; despite their structural constraints, they often exhibit competitive ratios that scale linearly with the number of vertices ($n$), similar to general graphs.
Conclusion and Future Directions
The study highlights that the "incremental tax" is a significant factor in online graph problems. While the paper provides comprehensive bounds, gaps remain in bounded-degree graphs (between $\Delta/2$ and $\Delta$). Future work may explore model variations, such as allowing limited removal of nodes from the dominating set at a cost, to better simulate real-world dynamic networks.
Summary updated