{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiatzjpb2e6ubijlgkulzpdfz4k6uclomtfyiifganqchhipovujzi",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mjj5oz3626n2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.13025v1",
  "publishedAt": "2026-04-15T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Bence Deák",
    "Péter Madarasi"
  ],
  "textContent": "**Authors:** Bence Deák, Péter Madarasi\n\nThe family of $(k,\\ell)$-sparse graphs, introduced by Lorea, plays a central role in combinatorial optimization and has a wide range of applications, particularly in rigidity theory. A key algorithmic problem is to decide whether a given graph is $(k,\\ell)$-sparse and, if not, to produce a vertex set certifying the failure of sparsity. While pebble game algorithms have long yielded $O(n^2)$-time recognition throughout the classical range $0 \\leq \\ell < 2k$, and $O(n^3)$-time algorithms in the extended range $2k \\leq \\ell < 3k$, substantially faster bounds were previously known only in a few special cases. We present new recognition algorithms for the parameter ranges $0 \\le \\ell \\le k$, $k < \\ell < 2k$, and $2k \\leq \\ell < 3k$. Our approach combines bounded-indegree orientations, reductions to rooted arc-connectivity, augmenting-path techniques, and a divide-and-conquer method based on centroid decomposition. This yields the first subquadratic, and in fact near-linear-time, recognition algorithms throughout the classical range when instantiated with the fastest currently available subroutines. Under purely combinatorial implementations, the running times become $O(n\\sqrt n)$ for $0 \\leq \\ell \\leq k$ and $O(n\\sqrt{n\\log n})$ for $k< \\ell <2k$. For $2k \\leq \\ell < 3k$, we obtain an $O(n^2)$-time algorithm when $\\ell \\leq 2k+1$ and an $O(n^2\\log n)$-time algorithm otherwise. In each case, the algorithm can also return an explicit violating set certifying that the input graph is not $(k,\\ell)$-sparse.",
  "title": "Asymptotically faster algorithms for recognizing $(k,\\ell)$-sparse graphs"
}