{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreihahaa36xsyzrskb4ifdzouaqvronrfa45tavv47wvd5qp6v3vumu",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mnz63upt2hz2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.11974v1",
  "publishedAt": "2026-06-11T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Malte Baumecker",
    "Rustam Latypov",
    "Yannic Maus",
    "Jara Uitto"
  ],
  "textContent": "**Authors:** Malte Baumecker, Rustam Latypov, Yannic Maus, Jara Uitto\n\nGiven a graph $G=(V,E)$, a $β$-ruling set is a subset of nodes $S\\subseteq V$ that is independent, and each node in $V$ is at distance at most $β$ from some node in $S$. In this paper, we present almost optimal distributed algorithms for finding $2$-ruling sets in the classical \\LOCAL model. Our main contribution is a randomized algorithm that w.h.p.\\ computes a $2$-ruling set on any $n$-node graph with bounded arboricity in $O(\\log \\log n)$ rounds. In fact, the algorithm works up to arboricity $O(\\log\\log n)$, improves exponentially over the prior state of the art that can be achieved by combining [Barenboim, Elkin, Pettie, Schneider; JACM'16], [Ghaffari; SODA'16], and [Bisht, Kothapalli and Pemmaraju; PODC'14], and nearly matches the lower bound of $Ω(\\log \\log n / \\log \\log \\log n)$ [Balliu, Brandt, Kuhn, Olivetti; FOCS'20]. The domination parameter $β=2$ is optimal for algorithms with runtime $\\log^{o(1)}n$: on graphs with arboricity $2$, there is a lower bound of $Ω(\\sqrt{\\log n})$ rounds for MIS (i.e., $β= 1$) [Khoury, Schild; FOCS'25]. Additionally, we obtain improved algorithms for larger arboricity. For general graphs with arboricity $α$, we present a randomized algorithm that computes a $2$-ruling set in $\\widetilde{O}(\\log^{5/8} α+\\log^{5/3} \\log n)$ rounds. This improves exponentially over the state of the art for a large range of non-constant arboricity. Our techniques extend beyond distributed computing. We present an $O(\\log \\log \\log n)$-round algorithm in the low-space Massively Parallel Computation (\\mpc) model that w.h.p.\\ computes a $2$-ruling set on any graph with arboricity up to $2^{poly (\\log \\log n)}$, improving exponentially over the state of the art from [Kothapalli, Pai, Pemmaraju; FSTTCS'20] combined with [Fischer, Giliberti, Grunau; SPAA'23].",
  "title": "Near-Optimal Distributed 2-Ruling Sets on Graphs with Low Arboricity"
}