Cyril Gavoille

Marthe Bonamy, Avinandan Das, Cyril Gavoille et al.

We prove that given any $α$-approximation LOCAL algorithm for Minimum Dominating Set (MDS) on planar graphs, we can construct an $f(g)$-round $(3α+1)$-approximation LOCAL algorithm for MDS on graphs embeddable in a given Euler genus-$g$ surface. Heydt et al. [European Journal of Combinatorics (2025)] gave an algorithm with $α=11+\varepsilon$, from which we derive a $(34 +\varepsilon)$-approximation algorithm for graphs of genus $g$, therefore improving upon the current state of the art of $24g+O(1)$ due to Amiri et al. [ACM Transactions on Algorithms (2019)]. It also improves the approximation ratio of $91+\varepsilon$ due to Czygrinow et al. [Theoretical Computer Science (2019)] in the particular case of orientable surfaces. We generalize this result into two directions: (1) by considering other graph problems studied in Distributed Computing such as Minimum $k$-Tuple Dominating Set, for which constant-round approximation algorithms were known for planar graphs, but not for graphs of bounded genus; and (2) by considering graph classes beyond bounded genus graphs, called locally nice, and relying on the asymptotic dimension of the class. We prove these results by a series of meta-theorems about cuttable minimization problems with constant-round approximation LOCAL algorithms. Roughly speaking, in cuttable problems, one can systematically extract small subgraphs whose solutions are in proportion to the global solution restricted to the neighbourhood of the subgraph.

Vida Dujmović, Gwenaël Joret, Cyril Gavoille et al.

We show that every proper minor-closed class of graphs admits a $(1+o(1))\log_2 n$-bit adjacency labelling scheme. Equivalently, for every proper minor-closed class $\mathcal{G}$ and every positive integer $n$ there exists an $n^{1+o(1)}$-vertex graph $U$ such that every $n$-vertex graph in $\mathcal{G}$ is isomorphic to an induced subgraph of $U$. Both results are optimal up to the lower order term.