Tight Bounds for Constant-Round Domination on Graphs of High Girth and Low Expansion

Summary

A long-standing open question is which graph class is the most general one permitting constant-time constant-factor approximations for dominating sets. The approximation ratio has been bounded by increasingly general parameters such as genus, arboricity, or expansion of the input graph. Amiri and Wiederhake considered k-hop domination in graphs of bounded k-hop expansion and girth at least 4k+3; the k-hop expansion f(k) of a graph family denotes the maximum ratio of edges to nodes that can be achieved by contracting disjoint subgraphs of radius k and deleting nodes. In this setting, these authors to obtain a simple O(k)-round algorithm achieving approximation ratio Θ(kf(k)). In this work, we study the same setting but derive tight bounds: - A Θ(kf(k))-approximation is possible in k, but not k−1 rounds. - In 3k rounds an O(k+f(k)k/(k+1))-approximation can be achieved. - No constant-round deterministic algorithm can achieve approximation ratio o(k+f(k)k/(k+1)). Our upper bounds hold in the port numbering model with small messages, while the lower bounds apply to local algorithms, i.e., with arbitrary message size and unique identifiers. This means that the constant-time approximation ratio can be \emph{sublinear} in the edge density of the graph, in a graph class which does not allow a constant approximation. This begs the question whether this is an artefact of the restriction to high girth or can be extended to all graphs of k-hop expansion f(k).