Matroid base optimization enables faster group label constraint solutions
Proximity Theorem and FPT Algorithm for Minimum Group-labeled Matroid Bases
Data Structures and Algorithms
Summary
Matroids are mathematical objects that describe structures with a notion of independence, like networks or graphs. This paper looks at ways to find the least costly group of elements (a "base") whose combined labels, from a group, avoid certain forbidden sums. The authors prove that only a limited number of swaps are needed to move from any cheapest base to one that avoids these sums and provide algorithms that quickly find such solutions when the size of the group or forbidden sets is small. This advances understanding and tools for optimizing with complex group-label constraints.
What this means in practice
- •For network designers: Identify cost-efficient network configurations that avoid specific aggregated constraints represented by group labels.
- •For combinatorial optimization engineers: Implement fixed-parameter tractable algorithms to compute minimal cost independent sets with group sum restrictions.
A theory result. No direct application yet.
Authors
Siyue Liu, Taihei Oki, Chao Xu
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.