



























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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。