Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
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 ${-\Delta,\ldots,\Delta}$ or more generally $m$-dimensional vectors of such discrete values. We resolve the parameterized complexity completely, by presenting an FPT algorithm parameterized by $\Delta$ and $m$ for arbitrary matroids. Prior to our work, no such algorithms were known even when weights are in ${0,1}$, or arbitrary $\Delta$ 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.
2404.03747v2
2024-10-27
979-8-3315-1674-1
1610
1620
REVIEWED
EPFL
| Event name | Event acronym | Event place | Event date |
FOCS | Chicago, United States | 2024-10-27 - 2024-10-30 | |