{"ID":2837209,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.20882","arxiv_id":"2511.20882","title":"Quadratic-Time Algorithm for the Maximum-Weight $(k, \\ell)$-Sparse Subgraph Problem","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 challenge is to compute a maximum-weight $(k, \\ell)$-sparse subgraph of a given edge-weighted graph. Although prior approaches have long provided an $O(nm)$-time solution, a previously proposed $O(n^2 + m)$ method was based on an incorrect analysis, leaving open whether this bound is achievable. We answer this question affirmatively by presenting the first $O(n^2 + m)$-time algorithm for computing a maximum-weight $(k, \\ell)$-sparse subgraph, which combines an efficient data structure with a refined analysis. This quadratic-time algorithm enables faster solutions to key problems in rigidity theory, including computing minimum-weight redundantly rigid and globally rigid subgraphs. Further applications include enumerating non-crossing minimally rigid frameworks and recognizing kinematic joints. Our implementation of the proposed algorithm is publicly available online.","short_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 challenge is to compute a maximum-weight $(k, \\ell)$-sparse subgraph of a given edge-weighted graph. Although prior ap...","url_abs":"https://arxiv.org/abs/2511.20882","url_pdf":"https://arxiv.org/pdf/2511.20882v1","authors":"[\"Bence Deák\",\"Péter Madarasi\"]","published":"2025-11-25T21:54:41Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CG\",\"cs.DM\",\"math.CO\"]","methods":"[]","has_code":false}