Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
<|reference_start|>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.<|reference_end|>
@article{eisenbrand2024sensitivity,,
    title={Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems},
    author={Friedrich Eisenbrand, Lars Rohwedder, Karol Wk{e}grzycki},
    journal={arXiv preprint arXiv:2404.03747},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.03747},
    primaryClass={cs.DS}
}