Proximity Theorem and FPT Algorithm for Minimum Group-labeled Matroid Bases
Abstract
Let M be a matroid, let ℓ:E(M)→ G be a labeling of its elements by an abelian group, and let F⊆ 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.
Related
- On minimum-size matroid counterexamples to the multiplicative Merino--Welsh inequality
- An existence result of a functional integral equation via Darbo type theorem and an iterative algorithm to solve it
- Breaking the Exponential Barrier: The First Polynomial-Time Algorithm for the Győri-Lovász Theorem
- Suspense and surprise in matroid bingo
- A weighted inequality for matroid flats and log-concavity of Whitney numbers
BibTeX
@misc{liu2026proximity,
title = {{Proximity Theorem and FPT Algorithm for Minimum Group-labeled Matroid Bases}},
author = {Siyue Liu and Taihei Oki and Chao Xu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.32798},
eprint = {2610.32798},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.32798},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Proximity Theorem and FPT Algorithm for Minimum Group-labeled Matroid Bases
AU - Siyue Liu
AU - Taihei Oki
AU - Chao Xu
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.32798
UR - https://arxiv.org/abs/2610.32798
AB - Let M be a matroid, let ℓ:E(M)→ G be a labeling of its elements by an abelian group, and let F⊆ 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.
ER -