Proximity Theorem and FPT Algorithm for Minimum Group-labeled Matroid Bases
\(\)
Let \(M\) be a matroid, let \(\ell:E(M)\to G\) be a labeling of its elements by an abelian group, and let \(F\subseteq G\) be finite. A base is \emph{\(F\)-avoiding} if the label sum of its elements is not in $F$. We prove that, for arbitrary costs, a min-cost \(F\)-avoiding base can be obtained from any min-cost base using at most $|F|$ exchanges. This resolves the weighted proximity conjecture by Hörsch, Imolay, Mizutani, Oki, and Schwarcz. Our main technical tool is to replace the assumption of Schrijver–Seymour Conjecture in Liu and Xu’s earlier work with Kemperman–Scherk Theorem. The proximity theorem combined with approaches in earlier work gives an FPT algorithm that finds a min-cost \(F\)-avoiding base parameterized by \(|G|\). We additionally give an FPT algorithm parameterized by \(|F|\), answering a question of Hörsch et al.