Optimal constant-round algorithms approximate dominating sets in special graph classes
Almost Optimal Constant-Round Approximation of Dominating Set in Graph Classes with Excluded Minors
Data Structures and AlgorithmsDistributed, Parallel, and Cluster ComputingDiscrete Mathematics
Summary
Finding a small set of points to control or monitor a network is a common problem called the dominating set problem. The authors found ways to quickly and nearly optimally pick such sets in certain kinds of networks that avoid complicated patterns, like planar graphs or graphs that exclude certain substructures. Their methods run in a fixed small number of steps regardless of network size and work deterministically or with randomness for better results. This work also settles long-standing questions about how well any fast algorithm can approximate these sets in these special kinds of graphs.
What this means in practice
- •For distributed systems engineers: Design efficient protocols for network control tasks on topologies that exclude certain complex structures, relying on predictable, constant-time approximations of dominating sets.
- •For network security teams: Deploy fast, reliable monitoring by selecting minimal sensor placements in planar or minor-free network models using guaranteed-approximate dominating sets.
Authors
Saeed Amiri, Sebastian Siebertz
Abstract
For every fixed proper minor-closed class $\mathscr C$ and every $ε>0$, we give a deterministic LOCAL algorithm that returns a dominating set of size at most $(2a(\mathscr C)+1+ε)γ_f(G)$ on every $G\in\mathscr C$. Here $a(\mathscr C)$ is the supremum edge-to-vertex ratio in~$\mathscr C$, and $γ_f(G)$ is the fractional domination number. The class also admits a deterministic $(1+ε)$-approximation for fractional dominating set and a randomized algorithm that always returns a dominating set and has expected size at most $(1+ε)γ(G)$. In each case, the number of rounds depends only on $\mathscr C$ and~$ε$. None of these algorithms requires the number of vertices or the maximum degree as part of the input. For planar graphs, this gives the deterministic guarantee $(7+ε)γ_f(G)$. Together with the lower bound of Hilke, Lenzen and Suomela, it determines the infimum of the deterministic constant-round approximation ratios for planar minimum dominating set as~$7$, settling a question that had remained open since their work. The corresponding infima, measured against the integral optimum, are $7$ for graphs of Euler genus at most any fixed $g\ge0$, $2t-3$ for $K_t$-minor-free graphs with $3\le t\le9$, and $2r+1$ for graphs of treewidth or pathwidth at most any fixed $r\ge1$. We also prove that, for every integer~\mbox{$r\ge1$}, no deterministic constant-round LOCAL algorithm achieves an approximation ratio below~\mbox{$2r+1$} on the $r$-th powers of paths, even when every vertex knows the number of vertices. This gives a new proof that the limiting constants are optimal for planar graphs, graphs of bounded treewidth or pathwidth, and $K_t$-minor-free graphs with $3\le t\le9$. For triangle-free planar graphs, the corresponding infimum is $5$.