Proximity Theorem and FPT Algorithm for Minimum Group-labeled Matroid Bases

Abstract

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 $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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Combinatorics

• arXiv preprint · 23 October 2026

  Implicit Neural Representations for Variational Problems on Graphons

  Taeyoung Kim, Jineon Baek, Joonkyung Lee and 1 other
• arXiv preprint · 25 October 2026

  Online Discrepancy of Sparse Random Vectors over Long Horizons

  Nicola Wengiel
• arXiv preprint · 23 October 2026

  Structure and Exact Certification of Nonnegative Tensor Decompositions

  Haoming Wang and Ming Yuan
• OpenAlex · 26 October 2026

  Mutation-acyclicity in rank four is decidable but not semialgebraic

  Kymani Armstrong-Williams, Edward Hirst, Blake Jackson and 1 other
• arXiv preprint · 27 October 2026

  Local-to-Global Theorems Based on Cones with Applications to Graph Coloring

  Anqi Li and Shayan Oveis Gharan

All new papers in Combinatorics