Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913478398181376 |
|---|---|
| author | Eisenbrand, Friedrich Rohwedder, Lars Węgrzycki, Karol |
| author_facet | Eisenbrand, Friedrich Rohwedder, Lars Węgrzycki, Karol |
| contents | We consider the problem of finding a basis of a matroid with weight exactly equal to a given target. Here weights can be discrete values from $\{-Δ,\ldots,Δ\}$ or more generally $m$-dimensional vectors of such discrete values. We resolve the parameterized complexity completely, by presenting an FPT algorithm parameterized by $Δ$ and $m$ for arbitrary matroids. Prior to our work, no such algorithms were known even when weights are in $\{0,1\}$, or arbitrary $Δ$ and $m=1$. Our main technical contributions are new proximity and sensitivity bounds for matroid problems, independent of the number of elements. These bounds imply FPT algorithms via matroid intersection. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_03747 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems Eisenbrand, Friedrich Rohwedder, Lars Węgrzycki, Karol Data Structures and Algorithms We consider the problem of finding a basis of a matroid with weight exactly equal to a given target. Here weights can be discrete values from $\{-Δ,\ldots,Δ\}$ or more generally $m$-dimensional vectors of such discrete values. We resolve the parameterized complexity completely, by presenting an FPT algorithm parameterized by $Δ$ and $m$ for arbitrary matroids. Prior to our work, no such algorithms were known even when weights are in $\{0,1\}$, or arbitrary $Δ$ and $m=1$. Our main technical contributions are new proximity and sensitivity bounds for matroid problems, independent of the number of elements. These bounds imply FPT algorithms via matroid intersection. |
| title | Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.03747 |