{"ID":2838389,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.16877","arxiv_id":"2511.16877","title":"Efficient Algorithms and Implementations for Extracting Maximum-Size $(k,\\ell)$-Sparse Subgraphs","abstract":"A multigraph $G = (V, E)$ is $(k, \\ell)$-sparse if every subset $X \\subseteq V$ induces at most $\\max\\{k|X| - \\ell, 0\\}$ edges. Finding a maximum-size $(k, \\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 $\\unicode{x2013}$ including edge-ordering, node-ordering, two-phase strategies, and pseudoforest-based initialization $\\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.","short_abstract":"A multigraph $G = (V, E)$ is $(k, \\ell)$-sparse if every subset $X \\subseteq V$ induces at most $\\max\\{k|X| - \\ell, 0\\}$ edges. Finding a maximum-size $(k, \\ell)$-sparse subgraph is a classical problem in rigidity theory and combinatorial optimization, with known polynomial-time algorithms. This paper presents a highly...","url_abs":"https://arxiv.org/abs/2511.16877","url_pdf":"https://arxiv.org/pdf/2511.16877v1","authors":"[\"Péter Madarasi\"]","published":"2025-11-21T01:01:23Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CG\",\"cs.DM\",\"math.CO\"]","methods":"[]","has_code":false}