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\)  [2]; 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 \(\varTheta (kf(k))\) . In this work, we study the same setting but derive tight bounds: – A \(\varTheta (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 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).

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • Christoph Lenzen,
  • Sophie Wenning

摘要

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\)  [2]; 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 \(\varTheta (kf(k))\) . In this work, we study the same setting but derive tight bounds: – A \(\varTheta (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 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).