Efficient Algorithms and Implementations for Extracting Maximum-Size $(k,\mathrm{\ell })$-Sparse Subgraphs

A multigraph $G=(V,E)$ is $(k,\mathrm{\ell })$-sparse if every subset $X\subseteq V$ induces at most $\max \{k\mathrm{\mid }X\mathrm{\mid }-\mathrm{\ell },0\}$ edges. Finding a maximum-size $(k,\mathrm{\ell })$-sparse subgraph is a classical problem in rigidity theory and combinatorial optimization, with known polynomial-time algorithms. This paper presents a highly efficient and flexible implementation of an augmenting path method, enhanced with a range of powerful practical heuristics that significantly reduce running time while preserving optimality. These heuristics $\text{unicode}x2013$ including edge-ordering, node-ordering, two-phase strategies, and pseudoforest-based initialization $\text{unicode}x2013$ steer the algorithm toward accepting more edges early in the execution and avoiding costly augmentations. A comprehensive experimental evaluation on both synthetic and real-world graphs demonstrates that our implementation outperforms existing tools by several orders of magnitude. We also propose an asymptotically faster algorithm for extracting an inclusion-wise maximal $(k,2k)$-sparse subgraph with the sparsity condition required only for node sets of size at least three, which is particularly relevant to 3D rigidity when $k=3$. We provide a carefully engineered implementation, which is publicly available online and is proposed for inclusion in the LEMON graph library.