Distributed algorithms find near-best dominating sets in planar graphs
Near-Optimal Distributed Domination in Planar Graphs
Data Structures and AlgorithmsDistributed, Parallel, and Cluster Computing
Summary
Finding a small set of key points (called a dominating set) that can 'cover' an entire network is useful but hard to do quickly, especially in large planar graphs which can be drawn on a flat surface without edges crossing. The authors improved a known method to find such sets much closer to the best possible size, using a distributed computing system where each part of the network works only with nearby information. Their new approach is nearly as good as theoretically possible and runs in a fixed, small number of communication steps. The technique also extends to more complex graph types with certain surface properties.
What this means in practice
- •For network administrators: Designing efficient monitoring or control points in planar network topologies using near-optimal distributed methods.
- •For distributed system engineers: Implementing fast, constant-round algorithms for minimal dominating sets without global topology knowledge in planar-like network environments.
Authors
Wojciech Wawrzyniak
Abstract
We give a deterministic $(8+\varepsilon)$-approximation for minimum dominating set on planar graphs in a constant number of rounds of the LOCAL model, for every $\varepsilon>0$. This improves the previous ratio $11+\varepsilon$ obtained by Heydt et al. The ratio is near-optimal in this model: its leading constant is only one above the known lower bound of $7$. Our result closes three quarters of the previous gap, reducing it from $4$ to $1$. Our main contribution is a sharp structural bound. For any dominating set $D$, assigning each vertex outside $D$ to a neighboring center gives disjoint owner blocks. If $k_x$ counts the other blocks containing a neighbor of $x$, then $\sum_{x\notin D}(k_x-2)^+\le(4|D|-12)^+$, where $z^+=\max\{z,0\}$. The bound holds for every such assignment, and equality holds for arbitrarily large minimum dominating sets. We use this bound in their three-phase framework, with new parameters and the same final linear-programming procedure. The algorithm requires neither a planar embedding nor the graph size, and its round bound depends only on $\varepsilon$. The transfer theorem of Bonamy et al. also gives a deterministic $(25+\varepsilon)$-approximation on graphs of bounded Euler genus, with a round bound depending only on $\varepsilon$ and the genus.