Asymptotically Faster Algorithms for Recognizing $(k,\ell )$-Sparse Graphs

Abstract

The 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\le \ell <2k$, and $O(n^3)$-time algorithms in the extended range $2k\le \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\le \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\le \ell \le k$ and $O(n\sqrt{n\log n})$ for $k<\ell <2k$. For $2k\le \ell <3k$, we obtain an $O(n^2)$-time algorithm when $\ell \le 2k+2$ 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.