{"id":"arxiv/2604.13025","url":"https://arxiv.org/abs/2604.13025","tags":["cs.DS","cs.DM","math.CO"],"score":0,"title":"Asymptotically Faster Algorithms for Recognizing $(k,\\ell)$-Sparse Graphs","domain":"cs.DS","source":"arxiv","authors":["Bence Deák","Péter Madarasi"],"reviews":0,"subject":"cs.DS","summary":"For fixed integers $k,\\ell$ with $0\\leq\\ell<3k$, we study the problem of deciding whether a graph is $(k,\\ell)$-sparse, a notion arising in combinatorial optimization and rigidity theory. Standard pebble-game algorithms take $O(n^2)$ time for $0\\leq\\ell<2k$ and $O(n^3)$ time for $2k\\leq\\ell<3k$, although faster algorithms were known for some parameter choices. We develop efficient recognition algorithms using bounded-indegree orientations, reductions to rooted arc-connectivity, augmenting paths, and centroid decomposition. For $0\\leq\\ell<2k$, they run in $O(n^{1+o(1)})$ time, yielding the…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-14","reactions":{}}