Distributed Approximation Algorithms for Minimum Dominating Set in Locally Nice Graphs
Marthe Bonamy, Cyril Gavoille, Timothé Picavet, Alexandra Wesolek · 2025
Read Distributed Approximation Algorithms for Minimum Dominating Set in Locally Nice Graphs by Marthe Bonamy, Cyril Gavoille, Timothé Picavet, Alexandra Wesolek (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-04960.txt.
Introduction
Marthe Bonamy and co-authors place watchmen on a network so every node is watched, using as few as possible, and they do it with no central commander. The minimum dominating set problem asks for the smallest such guard set. In the distributed setting each node may talk only to its neighbors, in rounds. Their 2025 paper gives short new proofs and faster algorithms for graphs that can be drawn on a surface of fixed genus.
The headline result is a constant-round distributed algorithm whose guard set stays within a fixed factor of optimal. In the refined version that factor improves on earlier work, to just above thirty-four. The machinery is borrowed cleverly: a good algorithm for flat, planar graphs, plus the fact that such surface graphs are, in a precise sense, two-dimensional at large scales.
Catalog record
| CREATOR | Marthe Bonamy, Cyril Gavoille, Timothé Picavet, Alexandra Wesolek |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-04960
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Distributed Approximation Algorithms for Minimum Dominating Set in Locally Nice Graphs Marthe Bonamy, Cyril Gavoille, Timothé Picavet, Alexandra Wesolek Abstract We give a new, short proof that graphs embeddable in a given Euler genus- g g surface admit a simple f ( g ) f(g) -round α \alpha -approximation distributed algorithm for Minimum Dominating Set (MDS), where the approximation ratio α ⩽ 906 \alpha\leqslant 906 . Using tricks from Heydt et al. [ European Journal of Combinatorics (2025)], we in fact derive that α ⩽ 34 + ε \alpha\leqslant 34+\varepsilon , therefore improving upon the current state of the art of 24 g + O ( 1 ) 24g+O(1) due to Amiri et al. [ ACM Transactions on Algorithms (2019)]. It also improves the approximation ratio of 91 + ε 91+\varepsilon due to Czygrinow et al. [ Theoretical Computer Science (2019)] in the particular case of orientable surfaces. All our distributed algorithms work in the deterministic LOCAL model. They do not require any preliminary embedding of the graph and only rely on two things: a LOCAL algorithm for MDS on planar graphs with “uniform” approximation guarantees and the knowledge that graphs embeddable in bounded Euler genus surfaces have asymptotic dimension 2 2 . More generally, our algorithms work in any graph class of bounded asymptotic dimension where “most vertices” are locally in a graph class that admits a LOCAL algorithm for MDS with uniform approximation guarantees. LaBRI, University of Bordeaux, CNRS, [email protected]://orcid.org/0000-0001-7905-8018 LaBRI, University of Bordeaux, CNRS, [email protected]://orcid.org/0000-0003-3671-8607 LaBRI, University of Bordeaux, CNRS, [email protected]://orcid.org/0000-0002-7129-0127 Institut für Mathematik, Technische Universität Berlin, [email protected]://orcid.org/0000-0003-4841-5937 ccs Theory of computation Design and analysis of algorithms keywords distributed algorithm, local model, dominating set, bounded genus graphs † † copyright: Marthe Bonamy, Cyril Gavoille, Timothé Picavet, and Alexandra Wesolek † † runningauthor: M. Bonamy et al. 1 Introduction Minimum Dominating Set (MDS) is a famous minimization problem on graphs, known to be NP-complete even in cubic planar graphs [ GJ79 , KYK80 ] . The goal is to find a smallest subset of vertices of the input graph that intersects all radius-1 balls of the graph. In this paper, we focus our attention on distributed algorithms that can approximate MDS on the graph underlying the topology of the network. Due to the covering property of a dominating set, the problem and its variants (like connected dominating set [ WAF02 ] ) get increasingly more attention in Networking, in particular for mobile and ad-hoc networks. Not only are mobile networks important for point-to-point communications, but specialized ad-hoc networks, such as sensor networks, are important for environmental monitoring tasks. We refer to [ KW05 , vRWZ09 ] for extended discussions about the motivations of MDS for routing purposes of such networks. We consider the standard LOCAL model. In this model, popularized by Linial [ Lin87 ] , nodes of the underlying network G work in synchronous rounds of communications between direct neighbors of G and are performed with messages of unlimited size. As the aim of this model is to study the “local nature” of a problem, the main complexity measure is the round complexity , the maximum number of rounds of communication to perform a given task in the network. In this model, approximating MDS up to a constant factor in general n -vertex graphs is known to require \Omega(\sqrt{\log{n}/\log\log{n}}\,) rounds [ KMW16 , CL20 ] . On the positive side, it is possible to (1+\varepsilon) -approximate MDS for any graph in \poly({\varepsilon}^{-1}\log{n}) rounds by combining the techniques of [ GKM17 ] and of [ RG20 , Corollary 3.11] . For specific graphs, better round complexities can be achieved; cf. [ LPW13 , Suo13 ] for a large collection of results (including unit-disk graphs, and planar graphs as a basis of the Gabriel graph model widely used in ad-hoc networks [ WY07 ] ). For instance, O(\log^{*}{n}) rounds suffice for planar graphs [ CHW08 ] , or more generally for K_{t} -minor-free graphs [ CHW18 ] and for sub-logarithmic expansion graphs [ ASS19 ] , and o(\log^{*}{n}) rounds are not sufficient to get a (1+\varepsilon) -approximation of MDS on cycles [ CHW08 ] or unit-disk graphs [ LW08 ] . So, achieving constant-round algorithms must be at the price of relaxing the (1+\varepsilon) approximation ratio. For planar graphs, the quest for constant-approximation and constant-round algorithms seems to start with [ LOW08 ] , with a 126 -approximation. Since then, a long line of research has been aimed at improving this ratio. In short, the best approximation ratio to date is 11+\varepsilon , due to [ HKOdM+25 ] . We refer to the nice survey of [ HKOdM+25 ] for planar graphs and sub-families, including lower bounds. In the meantime, the quest for constant-approximation ratio and constant-round distributed algorithms has been proposed for larger classes of graphs. However, very few examples are known of graph classes \mathscr{C}(p) , depending of some fixed parameter p , where Minimum Dominating Set can be solved by a LOCAL algorithm with round complexity f(p) and truly-constant approximation ratio (independent of p ). Larger graph classes that make good candidates for extending planar graphs are H -minor-free graphs, with some graph H not limited to K_{5} or K_{3,3} . For K_{p} -minor-free graphs, we only know of an exponential approximation ratio [ KSV21 , HKOdM+25 ] , whereas a linear approximation ratio could be possible. For K_{3,p} -minor-free graphs [ HKOdM+25 ] , the dependency is much better (it is linear in p ), but still not truly constant. Very recently, [ BGPW25 ] show that, for K_{2,p} -minor-free graphs, the approximation ratio is 50 regardless of the value of p . On the other end of the spectrum, the narrowest way to meaningfully extend planar graphs is through embeddable graphs 1 1 1 I.e., that can be drawn on the surface without edge crossing, like planar graphs for the sphere. on surfaces 2 2 2 That are compact, connected 2 -dimensional manifold without boundary. of Euler genus g . Such surfaces can be obtained from a sphere by adding g/2\geqslant 0 handles 3 3 3 By adding a handle, we mean that two disjoint disks of the sphere are replaced by a cylinder. (if they are orientable) or by adding g\geqslant 1 cross-caps 4 4 4 By adding a cross-cap, we mean that a disk of the sphere is replaced by a Möbius strip. (if they are nonorientable). The Euler genus of a graph G is the minimum number g such that G embedds on a surface of Euler genus g . In this context, [ ASS19 , Theorem 3.11] proposed an (24g+O(1)) -approximation algorithm with constant-round complexity (actually linear in g ). For graphs of orientable genus g , i.e., embeddable on an orientable surface of genus g , [ CHWW19 ] designed a constant-round algorithm that returns a dominating set of size at most 91\mathrm{M}+76g-66 , where \mathrm{M} is the optimal size. By adding a simple extra brute-force step in their algorithm, we can convert it into a (91+\varepsilon) -approximation 5 5 5 Observe that the diameter of each connected component of the graph is at most 3\mathrm{M} . So, each vertex check whether the diameter D of