Online Dominating Set

Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt, Michal Kotrbcík, Kim S. Larsen

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:

  1. Vertices arrive sequentially.
  2. Upon arrival, a vertex reveals all edges to previously arrived vertices.
  3. The algorithm must decide immediately whether to add vertices to the dominating set $D$.
  4. 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.

Table 1: Competitive ratios against the Optimal Incremental benchmark (OPT_INC) for various graph classes and DS variants.

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.

Table 2: Competitive ratios against the Optimal Offline benchmark (OPT_OFF) across different graph classes.

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

BibTeX
@inproceedings{boyar2016online,
  author = {Joan Boyar and Stephan J. Eidenbenz and Lene M. Favrholdt and Michal Kotrbcík and Kim S. Larsen},
  title = {{Online Dominating Set}},
  booktitle = {Algorithmica},
  year = {2016},
  doi = {10.1007/s00453-018-0519-1},
}
Figure