Source-linked AI summary
Proximity Theorem and FPT Algorithm for Minimum Group-labeled Matroid Bases
Siyue Liu, Taihei Oki, Chao Xu
TL;DR
The paper asks how close a minimum-cost base can be to the cheapest base whose label sum avoids a finite forbidden set. It proves that at most |F| exchanges suffice, using a weighted counting argument based on the Kemperman–Scherk theorem, and gives fixed-parameter algorithms in |F|.
Problem
The weighted proximity conjecture asks whether a min-cost F-avoiding base always lies within |F| exchanges of any min-cost base, when an F-avoiding base exists.
Source: §1 · pp. 1–2Method
The proof replaces the earlier Schrijver–Seymour conjecture assumption with a weighted counting argument using the Kemperman–Scherk theorem.
Source: §1.1 · p. 3, §3.2 · p. 8Results
Every min-cost base has a min-cost F-avoiding base within |F| exchanges, whenever an F-avoiding base exists.
Source: §1 · p. 2Takeaways & Limitations
The paper also provides an FPT algorithm for a min-cost F-avoiding base parameterized by |F|, answering a question of Hörsch et al. [HIM+24].
Source: §1 · p. 2The analogous proximity conjecture for simultaneous labelings remains open for arbitrary matroids.
Source: §1 · p. 2
Abstract
from arXiv · showhide
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\"orsch, 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\"orsch et al.
1 Introduction
The paper resolves the weighted proximity question for minimum-cost F-avoiding matroid bases and develops fixed-parameter algorithms for finding them. Its proof replaces a conjectural counting result with the Kemperman–Scherk theorem, while the introduction also records a sharp bound and an open multi-labeling question.
1 Introduction
- The weighted question asks how far an arbitrary minimum-cost base lies from the cheapest base whose label sum avoids F; prior weighted progress included the |F|=1 case [HIM+24].Earlier work also made substantial progress on the unweighted version, while the weighted conjecture had seen little progress.Source: §1 · pp. 1–2
- Every min-cost base is within |F| exchanges of a min-cost F-avoiding base, provided an F-avoiding base exists.The bound is sharp, and the result resolves the weighted proximity conjecture of Hörsch et al. [HIM+24].Source: §1 · p. 2
- The |F| exchange bound is sharp, and taking F=G\{g} recovers the unweighted proximity conjecture for g-bases.The sharpness example uses a rank-r partition matroid with F={0,1,...,k−1}, where every avoiding base must change at least k elements.Source: §1 · p. 2
- A min-cost F-avoiding base can be found in 2^O(|F|^2) · O(n^2 TWMI) time, giving fixed-parameter tractability in |F|.The paper also gives an FPT algorithm for finding an F-avoiding base; the proximity theorem alone yields an n^O(|F|)-query enumeration approach.Source: §1 · p. 2
- The analogous proximity conjecture for simultaneous labelings remains open for arbitrary matroids.The cited conjecture includes a lower bound of 2k−1 for k labelings.Source: §1 · p. 2
1.1 Techniques
- The proof uses the Kemperman–Scherk theorem to replace the Schrijver–Seymour conjecture assumption in the earlier approach.A weighted counting result for bases of bounded cost supplies the label-counting step used to establish proximity.Source: §1.1 · p. 3
- For finite G, proximity-based signature enumeration gives an O(|G|^(2|F|) TWMI)-time algorithm, fixed-parameter tractable in |G|.A signature records the number of base elements of each label, and each candidate signature is encoded by a partition matroid.Source: §1.1 · p. 4
1.2 Organization
- The paper proceeds from preliminaries to the proximity theorem, then presents the FPT algorithms for finding F-avoiding bases.Source: §1.2 · p. 5
2 Preliminaries
The preliminaries establish notation for label sums and matroid structure, then collect exchange tools and a sumset theorem used later. They also define F-avoidance and the low-cost label sets used in the counting argument.
2 Preliminaries
- For a subset X, ℓ(X) is the sum of its element labels, whereas ℓ[X] is the set of labels occurring on X.Source: §2 · p. 5
- A block matroid has a ground set partitionable into two bases; matroid restriction, deletion, contraction, direct sum, and components are also specified.Components correspond to connected components of the exchangeability graph of any base.Source: §2 · p. 5
- Bases admit a bijective pairing of their differing elements with valid single-element exchanges, and a multiple-exchange lemma swaps matched subsets while preserving both bases.Source: §2 · p. 5
- A circuit is minimally dependent, and each element outside a base has a unique fundamental circuit; the circuit lemma guarantees an exchange for every base element in that circuit.The rank of a set is the maximum size of an independent subset, and closure is the maximal superset of equal rank.Source: §2 · p. 5
- A base is F-avoiding when its label sum lies outside F, and ℓ≤θ(M) collects labels of bases costing at most θ.The Kemperman–Scherk theorem gives |P+Q|≥|P|+|Q|−1 when an element has a unique representation as p+q.Source: §2 · p. 6
3 Proximity Theorem
The section proves that any min-cost base is within |F| exchanges of a min-cost F-avoiding base, when one exists. It establishes color-counting bounds and uses them to derive the proximity result.
3.1 Counting colors in general matroids
- For each i, the label ℓ(B≥i) has a unique representation as s + h with s ∈ S_i+1 and h ∈ H_i.The argument constructs a competing base from any such representation and uses uniqueness of the minimum-cost base with label ℓ(B).Source: §3.1 · p. 6
3.2 Counting colors in block matroids
- In a rank-r block matroid with a min-cost base A and a unique min-cost ℓ(B)-base B, at least r + 1 distinct labels occur among bases of cost at most c(B).The block matroid has ground set partitioned into bases A and B.Source: §3.2 · p. 8
3 Proximity Theorem
- Every min-cost base A has a min-cost F-avoiding base B with d(A, B) ≤ |F|, provided an F-avoiding base exists.The proof reduces to a block matroid and bounds the number of relevant labels at cost at most c(B).Source: §3.3 · p. 9
3.3 Proof of the proximity theorem
- The proof contracts the common elements of the chosen bases, then applies the block-matroid color bound to obtain d(A0, B0) = r ≤ |F|.The translated forbidden set is F′ = F − ℓ(J), where J is the intersection of the original bases.Source: §3.3 · p. 9
4 FPT algorithms for finding F-avoiding bases
This section develops FPT algorithms parameterized by |F| for finding F-avoiding bases in unweighted and weighted settings, using signature enumeration and extending the approach to arbitrary costs. It proves that Solve(F) returns a min-cost F-avoiding base or correctly reports that none exists, and bounds its running time in terms of |F| and the matroid-intersection running time.
4 FPT algorithms for finding F-avoiding bases
- The section’s algorithms assume an independence oracle, unit-cost independence queries and group operations, and matroid-intersection running times TMI and TWMI.The cited examples give TMI = eO(nr^5/6) deterministically or eO(nr^3/4) randomized, and TWMI = eO(nr^2).Source: §4 · p. 10
4.1 Signature enumeration
- Signature enumeration searches d-close signatures over a prescribed label set Λ and uses matroid intersection with partition matroids to find a minimum-cost feasible base.The earlier enumeration of all bases within |F| exchanges is polynomial for fixed |F| but only XP in |F|; the new algorithms choose Λ bounded by functions of |F|.Source: §4.1 · pp. 10–11, §4 · p. 10
4.2 Unweighted algorithm
- The unweighted algorithm decides whether an F-avoiding base exists and returns one when it does, using a label-set reduction followed by signature enumeration.It either finds two same-component elements whose label difference is outside D = {g − h : g, h ∈ F}, yielding an avoiding base by exchange, or relabels elements so labels lie in D.Source: §4.2 · pp. 11–12
4.3.1 Preparation
- The preparation characterizes when a union of disjoint sets is exchangeable and factors exchangeability across strongly connected components of an auxiliary digraph.Lemma 18 requires no single-element exchanges between the specified parts; Lemma 19 says Z is exchangeable exactly when each component-associated Z(Q) is exchangeable.Source: §4.3.1 · pp. 12–13
4.3.2 Algorithm
- The weighted algorithm uses a recursive Solve(F) procedure and breaks cost ties so the minimum-cost base and each feasible minimum-cost F-avoiding base are unique.Its q-step derivations start at H and add or subtract elements of F − ℓ(A) at each step.Source: §4.3.2 · p. 13
4.3.3 Analysis
- The correctness analysis uses light exchanges to connect the search set K to the optimal avoiding base within 2|F| steps.When every light-exchange component meets or is adjacent to K, it traverses A △ B in at most 2d(A, B) ≤ 2|F| steps; otherwise, a component Z lets the algorithm recover B from a recursive solution Bf via Bf △ Z = B.Source: §4.3.3 · pp. 14–15
- Lemma 23 shows that Line 12 adds the min-cost F-avoiding base to the candidate set using 2|F|-step label derivations.The analysis bounds relevant graph paths by 2|F|; when a component is isolated from K, it uses a base Bf and a vertex in that component to capture the needed labels.Source: §4.3.3 · p. 16
- By induction on |F|, Solve(F) returns the min-cost F-avoiding base or correctly reports that none exists.The proof uses the induction hypothesis for recursive calls and shows that the optimum is either found by a single exchange or added to the candidate set by Lemma 23.Source: §4.3.3 · p. 17
- The running-time analysis gives 2^{O(|F|^2)} n^2 T_WMI for the algorithm, where T_WMI is the matroid-intersection running-time term.It bounds |K| by 2|F|(|F|−1), enumerates multisets for the derivations, and accounts for recursion over subsets of F.Source: §4.3.3 · p. 17