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.03747
Main Document
Submitted version (Preprint)
openaccess
CC BY
301.17 KB
Unknown
56dd3726cc5f8302db2588d54948a097