Quadratic-Time Algorithm for the Maximum-Weight $(k, \ell)$-Sparse Subgraph Problem
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915637956182016 |
|---|---|
| author | Deák, Bence Madarasi, Péter |
| author_facet | Deák, Bence Madarasi, Péter |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_20882 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quadratic-Time Algorithm for the Maximum-Weight $(k, \ell)$-Sparse Subgraph Problem Deák, Bence Madarasi, Péter Data Structures and Algorithms Computational Geometry Discrete Mathematics Combinatorics 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. |
| title | Quadratic-Time Algorithm for the Maximum-Weight $(k, \ell)$-Sparse Subgraph Problem |
| topic | Data Structures and Algorithms Computational Geometry Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2511.20882 |