betaFeedback

WorksComputer Science

Cogirth-Strength Ratios and Matroid Rank Reduction

Abstract

In the rank-pp reduction problem, we are given a matroid with nonnegative element weights and seek a minimum-weight set of elements whose deletion lowers the rank by at least pp. For graphic matroids, this is the minimum (p+1)(p+1)-cut problem. Chekuri, Quanrud, and Xu developed a tree-packing algorithm for minimum kk-cut, which relies on the fact that the minimum cut of a graph is at most twice its strength, the value of a maximum fractional packing of spanning trees. We generalize this approach from graphs to matroids. The matroid analogue of the minimum cut is the cogirth, the minimum weight of a cocircuit, and the analogue of graph strength is matroid strength, the value of a maximum fractional packing of bases. We show that if every matroid in a deletion-closed class has cogirth at most dd times its strength, then for every pp, the natural linear programming relaxation of rank-pp reduction is within a factor of dd of the optimum. As a result, repeatedly deleting a minimum-weight cocircuit gives a dd-approximation, and an optimal solution can be found deterministically in n(2d−1)p+O(1)n^{(2d-1)p+O(1)} time on nn elements. For graphs, d=2d=2 and our framework specializes to the tree-packing approach. As applications, we bound the cogirth-strength ratio for two broad classes, and both bounds are tight. For quasi-graphic matroids, which include graphic, bicircular, frame, and lifted-graphic matroids, the ratio is at most 22 for all weights, giving a 22-approximation and an exact n3p+O(1)n^{3p+O(1)}-time algorithm. For (k,ℓ)(k,\ell)-count matroids of hypergraphs with 0≤ℓ≤k0\le \ell\le k and edge size at most ss, the ratio is at most ksks under unit weights. This gives a ksks-approximation and an exact n(2ks−1)p+O(1)n^{(2ks-1)p+O(1)}-time algorithm for unweighted rank-pp reduction.

Introduction

Let MM be a matroid on a ground set EE with nonnegative element weights ww. In the rank-pp reduction problem, studied by Joret and Vetta [17], we seek a minimum-weight set of elements whose deletion lowers the rank of MM by at least pp. We write λp,w(M)\lambda_{p,w}(M) for its optimum. For the graphic matroid of a connected graph, deleting a set of edges lowers the rank by pp exactly when it leaves p+1p+1 components, so rank-pp reduction is the minimum (p+1)(p+1)-cut problem. For p=1p=1, it suffices to consider cocircuits, the inclusionwise minimal sets whose deletion lowers the rank. The minimum weight of a cocircuit is the weighted cogirth λw(M):=λ1,w(M)\lambda_w(M):=\lambda_{1,w}(M), the matroid analogue of the minimum cut.

A set lowers the rank by at least pp if and only if it contains at least pp elements of every base. Writing B(M)\mathcal{B}(M) for the set of bases of MM and x(S):=∑e∈Sxex(S):=\sum_{e\in S}x_e, this leads to the base-hitting LP

λp,w(M):=min⁡{∑e∈Ewexe | x∈[0,1]E, x(B)≥p for B∈B(M)}.(1)\lambda_{p,w}(M):=\min\left\{\sum_{e\in E}w_ex_e\ \middle|\ x\in[0,1]^E,\ x(B)\ge p\text{ for }B\in\mathcal{B}(M)\right\}. \tag*{(1)}

which generalizes the LP formulation of minimum kk-cut [6]. Its dual is

max⁡{p∑B∈B(M)yB−∑e∈Eze | y,z≥0, ∑B∋eyB−ze≤we for e∈E}.(2)\max\left\{p\sum_{B\in\mathcal{B}(M)}y_B-\sum_{e\in E}z_e\ \middle|\ y,z\ge0,\ \sum_{B\ni e}y_B-z_e\le w_e\text{ for }e\in E\right\}. \tag*{(2)}

For p=1p = 1, the upper bounds xe≤1x_e \le1 are redundant, so we may take z=0z = 0, and (2) asks for a maximum fractional packing of bases in which each element ee has capacity wew_e. Its optimum is the weighted strength σw(M)\sigma_w(M) [4, 19]. Since such a packing is also feasible for (2) for every pp, we have λp,w(M)≥λp,w∗(M)≥pσw(M)\lambda_{p,w}(M) \ge\lambda^*_{p,w}(M) \ge p\sigma_w(M).

In this paper we focus on the cogirth–strength ratio λw(M)/σw(M)\lambda_w(M)/\sigma_w(M), which is the integrality gap of (1) for p=1p = 1. For unit weights we drop the subscript ww and write ρ(M):=λ(M)/σ(M)\rho(M) := \lambda(M)/\sigma(M). In graphs, the theorem of Nash-Williams and Tutte [24, 30] implies that the minimum cut is at most twice the strength, and this fact underlies the tree-packing approach to minimum kk-cut [6]. For general matroids, the ratio can be arbitrarily large.1 We ask which matroids have bounded cogirth–strength ratio, and what a bounded ratio implies for rank-pp reduction when p>1p > 1.

Previous work. As a special case of rank reduction, the minimum kk-cut problem has been studied extensively [14, 26, 29, 16, 22, 15]. Two lines of work are most relevant to us. The first is the LP-based tree-packing approach of Chekuri, Quanrud, and Xu [6], which bounds the integrality gap of the spanning-tree relaxation of kk-cut and derives an exact enumeration algorithm from an optimal fractional tree packing. Our framework generalizes this approach from spanning trees to bases of matroids. The second is the series of works built on Karger’s random contraction algorithm [18, 20, 15], which very recently inspired a random deletion algorithm of Chandrasekaran, Chekuri, and Zhu [5]: it enumerates all α\alpha-approximate minimum circuits of an mm-element regular matroid in randomized mO(α)m^{O(\alpha)} time.

Beyond graphic matroids, Joret and Vetta [17] showed that rank reduction is polynomial-time solvable for partition matroids but NP-hard for intersections of two partition matroids. Other works have focused on cut problems for specific matroid classes. For a hypergraph HH and integers k,ℓk,\ell, the (k,ℓ)(k,\ell)-count matroid Mk,ℓ(H)M_{k,\ell}(H) has as independent sets the edge sets II such that ∣J∣≤k∣V(J)∣−ℓ|J| \le k|V(J)|-\ell for every nonempty J⊆IJ \subseteq I, where V(J)V(J) is the set of vertices met by JJ. Narayanan, Roy, and Patkar [23] studied approximation algorithms for hypergraph cut problems, and Fukunaga [12] gave an exact algorithm for hypergraph kk-cut when both kk and the maximum hyperedge size are fixed. Király [21] proved that the unweighted cogirth of Mk,k(H)M_{k,k}(H) can be computed in polynomial time without any bound on the hyperedge size. Cong, Xu, and Zhao [8] recently proved that computing the unweighted cogirth of the two-dimensional rigidity matroid of a simple graph, which is its (2,3)(2,3)-count matroid, is NP-hard. Geelen and Kapadia [13] gave randomized fixed-parameter tractable algorithms for computing the girth and the cogirth of rank-tt perturbed graphic matroids, and Cong, Xu, and Zhao [7] derandomized the cogirth algorithm. The relationship between cogirth and base packing has also been studied independently: Bailey, Newman, and Stevens [1] investigated matroids whose cogirth equals their integral base-packing number, and noted the difficulty of recognizing this equality in polynomial time for general matroids.

These results show that rank reduction behaves very differently across matroid classes, and most algorithms exploit structure specific to one class. It is natural to ask whether a single condition yields approximation guarantees and exact algorithms for many classes at once. We show that a bounded cogirth–strength ratio is such a condition.

Our contributions. Throughout, matroid MM has nn elements and is given by an independence oracle. Our first result shows that the integrality gap for p=1p = 1 controls the integrality gap for every pp. If λw(N)≤dσw(N)\lambda_w(N) \le d\sigma_w(N) for every positive-rank restriction NN of MM, then λp,w(M)≤dλp,w∗(M)\lambda_{p,w}(M) \le d\lambda^*_{p,w}(M) for every pp, and deleting a minimum-weight cocircuit pp times attains this bound (Theorem 1). Adapting the enumeration algorithm of Chekuri, Quanrud, and Xu [6], with bases in place of spanning trees and flats in place of graph components, we compute an optimal solution deterministically in n2d−1+p+O(1)n^{2d-1+p+O(1)} time, and implement the greedy dd-approximation in p n2d−1+O(1)p\,n^{2d-1+O(1)} time (Theorem 2). Neither algorithm needs to know dd. As a by-product, we decide in polynomial time whether the cogirth of a matroid equals its integral base-packing number, which resolves the recognition problem noted by Bailey, Newman, and Stevens [1].

We then bound the cogirth–strength ratio for two deletion-closed classes.

  • Quasi-graphic matroids, which include graphic, bicircular, frame, and lifted-graphic matroids [3], have weighted ratio at most 2 (Theorem 5). This gives a 2-approximation and an exact n3p+O(1)n^{3p+O(1)}-time algorithm for weighted rank-pp reduction.

  • For 0≤ℓ≤k0 \le\ell\le k, the count matroid Mk,ℓ(H)M_{k,\ell}(H) of a hypergraph with edges of size at most ss has ratio at most ksks under unit weights (Theorem 4). This gives a ksks-approximation and an exact n(2ks−1)p+O(1)n^{(2ks-1)p+O(1)}-time algorithm for unweighted rank-pp reduction.

Both bounds are tight. The one for count matroids follows from the subadditivity of the unweighted ratio under matroid union (Theorem 3).

Preliminaries

We assume familiarity with matroid theory and follow the notation of [25]. For a matroid MM on ground set E=E(M)E = E(M), we write rMr_M for its rank function, r(M):=rM(E)r(M) := r_M(E) for its rank, and B(M)B(M) for its set of bases. For X⊆EX \subseteq E, we write M∖XM \setminus X, M/XM/X, and M∣X:=M∖(E∖X)M|X := M \setminus(E \setminus X) for the matroids obtained by deleting XX, contracting XX, and restricting to XX, respectively. The closure cl⁡M(X)\operatorname{cl}_M(X) of X⊆EX \subseteq E is the set of elements whose addition to XX does not increase the rank. A flat is a set equal to its closure, and a hyperplane is a flat of rank r(M)−1r(M)-1. A cocircuit is a minimal set whose deletion decreases the rank. Cocircuits are exactly the complements of hyperplanes. For x∈REx \in\mathbb{R}^{E} and S⊆ES \subseteq E, we write x(S):=∑e∈Sxex(S) := \sum_{e \in S} x_e.

Let w:E→R≥0w : E \to\mathbb{R}_{\ge0} be weights; on minors of MM, ww denotes the restricted weights. The weighted cogirth λw(M)\lambda_w(M) is the minimum weight of a cocircuit. The weighted strength σw(M)\sigma_w(M) is the minimum of w(E∖F)r(M)−rM(F)\frac{w(E \setminus F)}{r(M)-r_M(F)} over all flats FF of rank less than r(M)r(M); by the base-packing theorem, it equals the optimum of (2) for p=1p = 1 (see § 3.1). Unless stated otherwise, all matroids considered are loopless and of positive rank. For unit weights we drop the subscript ww, and the cogirth–strength ratio is ρ(M):=λ(M)/σ(M)\rho(M) := \lambda(M)/\sigma(M). For weights with σw(M)>0\sigma_w(M) > 0, we write ρwwt(M):=λw(M)/σw(M)\rho_w^{\mathrm{wt}}(M) := \lambda_w(M)/\sigma_w(M), and the weighted cogirth–strength ratio ρwt(M)\rho^{\mathrm{wt}}(M) is the supremum of ρwwt(M)\rho_w^{\mathrm{wt}}(M) over all such weights.

Let M1,M2M_1, M_2 be matroids on disjoint ground sets E1,E2E_1, E_2, respectively. Their direct sum M=M1⊕M2M = M_1 \oplus M_2 is the matroid on E1∪E2E_1 \cup E_2 with independent sets I(M)={I1∪I2:I1∈I(M1), I2∈I(M2)}\mathcal{I}(M) = \{I_1 \cup I_2 : I_1 \in\mathcal{I}(M_1),\ I_2 \in\mathcal{I}(M_2)\}.

Lemma 1. Let M=M1⊕⋯⊕MmM = M_1 \oplus\cdots\oplus M_m and let w:E(M)→R≥0w : E(M) \to\mathbb{R}_{\ge0}. Then λw(M)=min⁡iλw(Mi)\lambda_w(M) = \min_i \lambda_w(M_i) and σw(M)=min⁡iσw(Mi)\sigma_w(M) = \min_i \sigma_w(M_i).

Proof. The cocircuits of MM are exactly the cocircuits of the summands MiM_i, giving λw(M)=min⁡iλw(Mi)\lambda_w(M) = \min_i \lambda_w(M_i).

Every flat of MM has the form F=⋃iFiF = \bigcup_i F_i, where FiF_i is a flat of MiM_i, and rM(X)=∑irMi(X∩E(Mi))r_M(X) = \sum_i r_{M_i}(X \cap E(M_i)) for all X⊆E(M)X \subseteq E(M). If rM(F)<r(M)r_M(F) < r(M), then

w(E(M)∖F)r(M)−rM(F)=∑iw(E(Mi)∖Fi)∑i(r(Mi)−rMi(Fi))≥min⁡i:Fi≠E(Mi)w(E(Mi)∖Fi)r(Mi)−rMi(Fi)≥min⁡iσw(Mi).\frac{w(E(M) \setminus F)}{r(M)-r_M(F)} = \frac{\sum_i w(E(M_i) \setminus F_i)}{\sum_i (r(M_i)-r_{M_i}(F_i))} \ge \min_{i:F_i\ne E(M_i)} \frac{w(E(M_i) \setminus F_i)}{r(M_i)-r_{M_i}(F_i)} \ge \min_i \sigma_w(M_i).

Equality holds when FiF_i attains σw(Mi)\sigma_w(M_i) for a minimizing ii and Fj=E(Mj)F_j = E(M_j) for j≠ij \ne i. Hence σw(M)=min⁡iσw(Mi)\sigma_w(M) = \min_i \sigma_w(M_i). □

In particular, ρwwt(M)≤max⁡iρwwt(Mi)\rho_w^{\mathrm{wt}}(M) \le\max_i \rho_w^{\mathrm{wt}}(M_i) whenever σw(M)>0\sigma_w(M) > 0, since any MiM_i attaining σw(M)\sigma_w(M) has cogirth at least λw(M)\lambda_w(M).

Rank-pp reduction

Throughout this section, let p∈Z+p \in\mathbb{Z}_{+}, and let MM be an nn-element matroid of rank at least pp with element weights w:E(M)→R≥0w : E(M) \to\mathbb{R}_{\geq0}. Rank-pp reduction asks for a minimum-weight set whose deletion lowers the rank by at least pp. A set S⊆E(M)S \subseteq E(M) is a pp-cocycle if E(M)∖SE(M) \setminus S is a flat and rM(E(M)∖S)≤r(M)−pr_M(E(M) \setminus S) \leq r(M) - p.

Every rank-pp reduction set RR contains the pp-cocycle E(M)∖cl⁡M(E(M)∖R)E(M) \setminus\operatorname{cl}_M(E(M) \setminus R). Hence rank-pp reduction is the minimum-weight pp-cocycle problem. We write λp,w(M)\lambda_{p,w}(M) for its optimum.

The base-hitting LP and its gap

We bound the integrality gap of (1) by following the greedy algorithm that repeatedly deletes a minimum-weight cocircuit. Recall that λ1,w∗(M)=σw(M)\lambda^*_{1,w}(M) = \sigma_w(M) [27 Section 42.4]. Deleting a cocircuit CC lowers the rank by exactly one, so CC together with any rank-(p−1)(p-1) reducing set of M∖CM \setminus C is a rank-pp reducing set of MM. The next lemma is the fractional counterpart: deleting CC and lowering the target by one decreases the LP optimum by at least σw(M)\sigma_w(M).

Lemma 2. Let CC be a cocircuit of MM. Then λ1,w∗(M)+λp−1,w∗(M∖C)≤λp,w∗(M)\lambda^*_{1,w}(M) + \lambda^*_{p-1,w}(M \setminus C) \leq\lambda^*_{p,w}(M), with the convention λ0,w∗≡0\lambda^*_{0,w} \equiv0.

Proof. The case p=1p = 1 is immediate, so assume p≥2p \geq2. Put E:=E(M)E := E(M), let xx be any feasible solution to the rank-pp LP (1) on MM, and set a:=min⁡e∈Cxe∈[0,1]a := \min_{e \in C} x_e \in[0,1]. Extend x′:=p−1p−ax∣E∖Cx' := \frac{p-1}{p-a}x|_{E\setminus C} by zero on CC. Since 0≤a≤10 \leq a \leq1 and p≥2p \geq2, we have 0≤x′≤x≤10 \leq x' \leq x \leq1 coordinatewise, so both x′x' and x−x′x-x' lie in [0,1]E[0,1]^E.

Since CC is a cocircuit, E∖CE\setminus C is a hyperplane, so every base B′B' of M∖CM \setminus C extends to a base of MM by adding any e∈Ce \in C. Choosing e∈Ce \in C with xe=ax_e = a gives x(B′)≥p−ax(B') \geq p-a and hence x′(B′)≥p−1x'(B') \geq p-1, so x′∣E∖Cx'|_{E\setminus C} is feasible for the rank-(p−1)(p-1) LP on M∖CM \setminus C.

Moreover, every base BB of MM meets the cocircuit CC, so x(B∩C)≥ax(B \cap C) \geq a. Together with x(B)≥px(B) \geq p and 1−a≥01-a \geq0, this gives

(x−x′)(B)=1−ap−ax(B∖C)+x(B∩C)=(1−a)x(B)+(p−1)x(B∩C)p−a≥(1−a)p+(p−1)ap−a=1,\begin{aligned} (x-x')(B) &= \frac{1-a}{p-a}x(B\setminus C)+x(B\cap C) \\ &= \frac{(1-a)x(B)+(p-1)x(B\cap C)}{p-a} \\ &\geq\frac{(1-a)p+(p-1)a}{p-a}=1, \end{aligned}

so x−x′x-x' is feasible for the rank-one LP on MM. Since x′x' vanishes on CC, the objective values of x−x′x-x' and x′∣E∖Cx'|_{E\setminus C} sum to ∑e∈Ewexe\sum_{e\in E} w_e x_e, giving λ1,w∗(M)+λp−1,w∗(M∖C)≤∑e∈Ewexe\lambda^*_{1,w}(M)+\lambda^*_{p-1,w}(M\setminus C) \leq\sum_{e\in E}w_e x_e. Minimizing over feasible xx proves the lemma.

Theorem 1. Suppose d≥1d \geq1 satisfies λw(N)≤dσw(N)\lambda_w(N) \leq d \sigma_w(N) for every positive-rank restriction NN of MM. Repeatedly deleting a minimum-weight cocircuit for pp steps produces a pp-cocycle SS with w(S)≤dλp,w∗(M)w(S) \leq d\lambda^*_{p,w}(M), where λp,w∗(M)\lambda^*_{p,w}(M) is the optimum of (1).

Proof. Put M0:=MM_0 := M. For i=0,…,p−1i = 0,\ldots,p-1, let CiC_i be a minimum-weight cocircuit of MiM_i and put Mi+1:=Mi∖CiM_{i+1} := M_i \setminus C_i. The sets E(Mi)E(M_i) form a chain of flats of MM with ranks r(M)−ir(M)-i, so S:=⋃i=0p−1CiS := \bigcup_{i=0}^{p-1} C_i is a pp-cocycle. Since λw(Mi)≤dσw(Mi)\lambda_w(M_i) \leq d\sigma_w(M_i), Lemma 2 gives

w(S)=∑i=0p−1w(Ci)≤d∑i=0p−1λ1,w∗(Mi)≤d∑i=0p−1(λp−i,w∗(Mi)−λp−i−1,w∗(Mi+1))=dλp,w∗(M).\begin{aligned} w(S)=\sum_{i=0}^{p-1}w(C_i)\leq d\sum_{i=0}^{p-1}\lambda^*_{1,w}(M_i) \\ &\leq d\sum_{i=0}^{p-1}\left(\lambda^*_{p-i,w}(M_i)-\lambda^*_{p-i-1,w}(M_{i+1})\right) \\ &=d\lambda^*_{p,w}(M). \end{aligned}

If every member MM of a deletion-closed class satisfies ρwt(M)≤d\rho^{\mathrm{wt}}(M) \le d, then the weighted LP gap on that class is at most dd.

Enumeration from the LP gap

The next theorem adapts the LP enumeration of Chekuri, Quanrud, and Xu [6], with bases in place of spanning trees and flats in place of graph components.

Theorem 2. Given an independence oracle for MM, a minimum-weight pp-cocycle is computable deterministically in n(2ρp,w−1)p+O(1)n^{(2\rho_{p,w}-1)p+O(1)} time, where ρp,w:=λp,w(M)λp,w∗(M)\rho_{p,w} := \frac{\lambda_{p,w}(M)}{\lambda^*_{p,w}(M)} is not part of the input.

Proof. Assume λp,w∗(M)>0\lambda^*_{p,w}(M)>0. First we compute λp,w∗(M)\lambda^*_{p,w}(M) and an optimal dual solution (y,z)(y,z) of (2). Separation over the base constraints of (1) computes a minimum-xx-weight base and reports a violation exactly when its xx-weight is below pp, i.e., there exists a base BB of MM with x(B)<px(B)<p. So Schrijver’s optimization–separation theorem [27] recovers an optimal dual supported on at most nn base constraints. Since the dual LP has nn constraints, we may choose an optimal basic feasible solution (y,z)(y,z) with at most nn positive variables. Let B+:={B∈B(M):yB>0}\mathcal{B}^{+}:=\{B\in\mathcal{B}(M):y_B>0\} and β:=∑ByB\beta:=\sum_{B}y_B. Then ∣B+∣≤n|\mathcal{B}^{+}|\le n, and by strong duality, λp,w∗(M)=pβ−∑eze≤pβ\lambda^*_{p,w}(M)=p\beta-\sum_e z_e\le p\beta. Since λp,w∗(M)>0\lambda^*_{p,w}(M)>0, we obtain β≥λp,w∗(M)/p>0\beta\ge\lambda^*_{p,w}(M)/p>0.

Fix any pp-cocycle AA, so w(A)≥λp,w∗(M)w(A)\ge\lambda^*_{p,w}(M). Sampling B∈B+B\in\mathcal{B}^{+} with probability yB/βy_B/\beta, dual feasibility gives

E[∣A∩B∣]=1β∑e∈A∑B∋eyB≤w(A)+z(A)β≤p+w(A)−λp,w∗(M)β≤pw(A)λp,w∗(M).\mathbb{E}[|A\cap B|]=\frac{1}{\beta}\sum_{e\in A}\sum_{B\ni e}y_B\le\frac{w(A)+z(A)}{\beta}\le p+\frac{w(A)-\lambda^*_{p,w}(M)}{\beta}\le\frac{p w(A)}{\lambda^*_{p,w}(M)}.

so some B∈B+B\in\mathcal{B}^{+} has ∣A∩B∣≤⌊pw(A)/λp,w∗(M)⌋|A\cap B|\le\left\lfloor p w(A)/\lambda^*_{p,w}(M)\right\rfloor.

Every pp-cocycle meets every base in at least pp elements. Fix B∈B+B\in\mathcal{B}^{+} and S⊆BS\subseteq B with ∣S∣≥p|S|\ge p. We list all pp-cocycles AA with A∩B=SA\cap B=S as follows. For such an AA, the flat E(M)∖AE(M)\setminus A contains B∖SB\setminus S, so F:=E(M)∖(A∪B)F:=E(M)\setminus(A\cup B) is a flat of M/(B∖S)M/(B\setminus S) disjoint from SS with

rM/(B∖S)(F)=rM(E(M)∖A)−rM(B∖S)≤(r(M)−p)−(r(M)−∣S∣)=∣S∣−p.r_{M/(B\setminus S)}(F)=r_M(E(M)\setminus A)-r_M(B\setminus S)\le(r(M)-p)-(r(M)-|S|)=|S|-p.

Conversely, for every such flat FF, the set (B∖S)∪F(B\setminus S)\cup F is a flat of MM of rank at most r(M)−pr(M)-p, and its complement is a pp-cocycle AA with A∩B=SA\cap B=S. Every flat of rank at most ∣S∣−p|S|-p is the closure of an independent set of size at most ∣S∣−p|S|-p, so computing the closures of all such sets in M/(B∖S)M/(B\setminus S) lists all such AA in n∣S∣−p+O(1)n^{|S|-p+O(1)} time.

For t=p,p+1,…t=p,p+1,\ldots, list the pp-cocycles AA with ∣A∩B∣≤t|A\cap B|\le t for some B∈B+B\in\mathcal{B}^{+}, let mtm_t be the minimum weight found so far, and halt once t≥⌊pmt/λp,w∗(M)⌋t\ge\left\lfloor p m_t/\lambda^*_{p,w}(M)\right\rfloor. By the averaging bound, every pp-cocycle AA is listed by threshold ⌊pw(A)/λp,w∗(M)⌋\left\lfloor p w(A)/\lambda^*_{p,w}(M)\right\rfloor. Hence, when the algorithm halts, every pp-cocycle of weight at most mtm_t has been listed, so mt=λp,w(M)m_t=\lambda_{p,w}(M). Moreover, a minimum-weight pp-cocycle is listed by threshold ⌊pρp,w⌋\lfloor p\rho_{p,w}\rfloor, after which mt=λp,w(M)m_t=\lambda_{p,w}(M), so the algorithm halts by t=⌊pρp,w⌋t=\lfloor p\rho_{p,w}\rfloor. Threshold tt costs n⋅nt⋅nt−p+O(1)n\cdot n^t\cdot n^{t-p+O(1)}, and summing up to t=⌊pρp,w⌋t=\lfloor p\rho_{p,w}\rfloor gives n(2ρp,w−1)p+O(1)n^{(2\rho_{p,w}-1)p+O(1)} time. □

Suppose λw(N)≤d σw(N)\lambda_w(N)\le d\,\sigma_w(N) for every positive-rank restriction NN of MM. Then ρp,w≤d\rho_{p,w}\le d by Theorem 1, so Theorem 2 solves rank-pp reduction exactly in n(2d−1)p+O(1)n^{(2d-1)p+O(1)} time. Moreover, each step of the greedy algorithm in Theorem 1 needs a minimum-weight cocircuit of some restriction NN, which Theorem 2 with p=1p=1 finds in n2d−1+O(1)n^{2d-1+O(1)} time since ρ1,w=λw(N)/σw(N)≤d\rho_{1,w}=\lambda_w(N)/\sigma_w(N)\le d. Hence the greedy dd-approximation runs in pn2d−1+O(1)p n^{2d-1+O(1)} time. Neither algorithm needs to know dd.

For unit weights, the case p=1p=1 also decides in polynomial time whether λ(M)\lambda(M) equals the maximum number of disjoint bases of MM, which is ⌊σ(M)⌋\lfloor\sigma(M)\rfloor by Edmonds’ base packing theorem [9]; this resolves the recognition problem noted by Bailey, Newman, and Stevens [1]. Since λ(M)≥σ(M)\lambda(M)\ge\sigma(M), equality holds only if σ(M)\sigma(M) is an integer and λ(M)=σ(M)\lambda(M)=\sigma(M). In that case every minimum cocircuit AA has ∣A∣=σ(M)=λ1∗(M)|A| = \sigma(M) = \lambda_1^*(M), so the averaging bound in the proof of Theorem 2 shows that AA meets some B∈B+B \in\mathcal{B}^+ in exactly one element. Hence it suffices to run the enumeration with threshold t=1t = 1, which takes polynomial time, and compare the minimum found with σ(M)\sigma(M).

Matroid union

For matroids M1,…,MmM_1,\ldots,M_m on a common ground set EE, their matroid union M1∨⋯∨MmM_1 \vee\cdots\vee M_m is a matroid on EE with independent sets {I1∪⋯∪Im:Ii∈I(Mi), 1≤i≤m}\{I_1 \cup\cdots\cup I_m : I_i \in\mathcal{I}(M_i),\ 1 \leq i \leq m\}.

Theorem 3. Let M1,…,MmM_1,\ldots,M_m be matroids on the same ground set EE, and put M:=M1∨⋯∨MmM := M_1 \vee\cdots\vee M_m. Then

ρ(M)≤∑i=1mρ(Mi).\rho(M) \leq\sum_{i=1}^{m} \rho(M_i).

Proof. Put h:=∑i1/σ(Mi)h := \sum_i 1/\sigma(M_i). We first prove σ(M)≥1/h\sigma(M) \geq1/h. If h≥1h \geq1, this follows from σ(M)≥1\sigma(M) \geq1. Assume h<1h < 1, and write r,rir,r_i for the rank functions of M,MiM,M_i. For A⊆EA \subseteq E, choose Y⊆AY \subseteq A attaining the matroid-union rank formula r(A)=∣A∖Y∣+∑iri(Y)r(A) = |A \setminus Y| + \sum_i r_i(Y) [25 Theorem 12.3.1]. The strength formula gives ri(E)−ri(Y)≤∣E∖Y∣/σ(Mi)r_i(E) - r_i(Y) \leq|E \setminus Y|/\sigma(M_i), also when the left side is zero. Since r(E)≤∑iri(E)r(E) \leq\sum_i r_i(E),

r(E)−r(A)≤∑i(ri(E)−ri(Y))−∣A∖Y∣≤h∣E∖Y∣−∣A∖Y∣=h∣E∖A∣+(h−1)∣A∖Y∣≤h∣E∖A∣.\begin{aligned} r(E) - r(A) &\leq\sum_i \bigl(r_i(E) - r_i(Y)\bigr) - |A \setminus Y| \\ &\leq h|E \setminus Y| - |A \setminus Y| \\ &= h|E \setminus A| + (h-1)|A \setminus Y| \\ &\leq h|E \setminus A|. \end{aligned}

Taking AA to be a flat of MM with r(A)<r(E)r(A) < r(E) gives ∣E∖A∣/(r(E)−r(A))≥1/h|E \setminus A|/(r(E)-r(A)) \geq1/h, so σ(M)≥1/h\sigma(M) \geq1/h. Every base of MM spans each MiM_i: otherwise, an element outside its MiM_i-closure could be added to its MiM_i-part in a union decomposition. Thus every cocircuit of MiM_i meets every base of MM and hence contains a cocircuit of MM, giving λ(M)≤λ(Mi)\lambda(M) \leq\lambda(M_i). Combining the two bounds yields ρ(M)≤λ(M)∑i1/σ(Mi)≤∑iρ(Mi)\rho(M) \leq\lambda(M) \sum_i 1/\sigma(M_i) \leq\sum_i \rho(M_i).

Write D(M):=max⁡X⊆E(M){ρ(M∣X):rM(X)>0}D(M) := \max_{X \subseteq E(M)}\{\rho(M|X) : r_M(X) > 0\}. Restriction commutes with matroid union, so applying the theorem to the positive-rank restrictions of the summands gives D(M1∨⋯∨Mm)≤∑iD(Mi)D(M_1 \vee\cdots\vee M_m) \leq\sum_i D(M_i). Thus the greedy algorithm of Theorem 1 gives a ∑iD(Mi)\sum_i D(M_i)-approximation for unweighted rank reduction on the union.

Lower-range count matroids

Throughout this section, fix integers k≥1k \geq1, 0≤ℓ≤k0 \leq\ell\leq k, and s≥2s \geq2, and let H=(V,E)H = (V,E) be a hypergraph. For I⊆EI \subseteq E, let V(I)V(I) be the set of vertices met by II. Recall that the (k,ℓ)(k,\ell)-count matroid Mk,ℓ(H)M_{k,\ell}(H) has as its independent sets those I⊆EI \subseteq E satisfying ∣J∣≤k∣V(J)∣−ℓ|J| \leq k|V(J)| - \ell for every nonempty J⊆IJ \subseteq I. We write Kv(s)K_v^{(s)} for the complete ss-uniform hypergraph on vv vertices, and Kv:=Kv(2)K_v := K_v^{(2)}.

Theorem 4. If HH has edge size at most ss, then ρ(Mk,ℓ(H))≤ks\rho(M_{k,\ell}(H)) \leq ks. Moreover, ρ(Mk,ℓ(Kv(s)))→ks\rho(M_{k,\ell}(K_v^{(s)})) \to ks as v→∞v \to\infty.

Since lower-range count matroids are closed under deletion, Theorem 1 and Theorem 2, with unit weights, give a ksks-approximation for every feasible rank loss p≥1p \geq1 and exact rank-pp reduction in n(2ks−1)p+O(1)n^{(2ks-1)p+O(1)} time.

By the maps-and-trees decomposition [28 Theorem 1.7 and Proposition 4.3], Mk,ℓ(H)M_{k,\ell}(H) is the matroid union of ℓ\ell copies of the hypergraphic matroid M1,1(H)M_{1,1}(H) and k−ℓk-\ell copies of M1,0(H)M_{1,0}(H), the transversal matroid of the edge–vertex incidence bipartite graph:

Mk,ℓ(H)=⋁ℓM1,1(H)∨⋁k−ℓM1,0(H).(3)M_{k,\ell}(H)=\bigvee_{\ell}M_{1,1}(H)\vee\bigvee_{k-\ell}M_{1,0}(H). \tag*{(3)}

By Theorem 3, the upper bound ρ(Mk,ℓ(H))≤ks\rho(M_{k,\ell}(H))\le ks reduces to bounding the ratios of M1,1(H)M_{1,1}(H) and M1,0(H)M_{1,0}(H) by ss.

The upper bound

For M1,1(H)M_{1,1}(H), we translate the known hypergraph partition bound into a cogirth–strength bound.

Proposition 1. If HH has edge size at most ss, then ρ(M1,1(H))≤s\rho(M_{1,1}(H))\le s.

Proof. Write M:=M1,1(H)M:=M_{1,1}(H), r:=rMr:=r_M, and v:=∣V(H)∣v:=|V(H)|. Since r(M)>0r(M)>0, we have v≥2v\ge2. For a partition P\mathcal{P} of V(H)V(H), let δH(P)\delta_H(\mathcal{P}) be the set of edges meeting more than one part, and set τ(H):=min⁡∣P∣≥2∣δH(P)∣/(∣P∣−1)\tau(H):=\min_{|\mathcal{P}|\ge2}|\delta_H(\mathcal{P})|/(|\mathcal{P}|-1). By the hypergraphic rank formula of Frank, Király, and Kriesell [11], r(A)=min⁡P(v−∣P∣+∣A∩δH(P)∣)r(A)=\min_{\mathcal{P}}\left(v-|\mathcal{P}|+|A\cap\delta_H(\mathcal{P})|\right) for every A⊆EA\subseteq E. In particular, r(E)≤v−1r(E)\le v-1, with equality if and only if τ(H)≥1\tau(H)\ge1.

Suppose first that τ(H)≥1\tau(H)\ge1, so r(E)=v−1r(E)=v-1. We show that σ(M)=τ(H)\sigma(M)=\tau(H). For any A⊆EA\subseteq E with r(A)<r(E)r(A)<r(E), choose a partition P\mathcal{P} attaining r(A)=v−∣P∣+∣A∩δH(P)∣r(A)=v-|\mathcal{P}|+|A\cap\delta_H(\mathcal{P})|. Since ∣δH(P)∣≥∣P∣−1|\delta_H(\mathcal{P})|\ge|\mathcal{P}|-1, subtracting ∣A∩δH(P)∣|A\cap\delta_H(\mathcal{P})| from numerator and denominator shows

∣E∖A∣r(E)−r(A)≥∣δH(P)∖A∣∣P∣−1−∣A∩δH(P)∣≥∣δH(P)∣∣P∣−1≥τ(H).\frac{|E\setminus A|}{r(E)-r(A)} \ge \frac{|\delta_H(\mathcal{P})\setminus A|}{|\mathcal{P}|-1-|A\cap\delta_H(\mathcal{P})|} \ge \frac{|\delta_H(\mathcal{P})|}{|\mathcal{P}|-1} \ge\tau(H).

Conversely, let P\mathcal{P} be a partition attaining τ(H)\tau(H), and put A:=E∖δH(P)A:=E\setminus\delta_H(\mathcal{P}). Since r(A)≤v−∣P∣r(A)\le v-|\mathcal{P}|, we have r(E)−r(A)≥∣P∣−1r(E)-r(A)\ge|\mathcal{P}|-1, and taking F:=cl⁡M(A)F:=\operatorname{cl}_M(A) gives

σ(M)≤∣E∖F∣r(E)−r(F)≤∣δH(P)∣∣P∣−1=τ(H).\sigma(M)\le\frac{|E\setminus F|}{r(E)-r(F)} \le\frac{|\delta_H(\mathcal{P})|}{|\mathcal{P}|-1} =\tau(H).

Hence σ(M)=τ(H)\sigma(M)=\tau(H). By a result of Baïou and Barahona [2], there is a bipartition P\mathcal{P} of V(H)V(H) with ∣δH(P)∣≤s(1−1/v)τ(H)|\delta_H(\mathcal{P})|\le s(1-1/v)\tau(H). Deleting δH(P)\delta_H(\mathcal{P}) lowers the rank of MM to at most v−2v-2, so λ(M)≤∣δH(P)∣<sσ(M)\lambda(M)\le|\delta_H(\mathcal{P})|<s\sigma(M).

Having established the bound when τ(H)≥1\tau(H)\ge1, we now consider general HH. Choose a partition P\mathcal{P} attaining r(E)=v−∣P∣+∣δH(P)∣r(E)=v-|\mathcal{P}|+|\delta_H(\mathcal{P})|, and for each X∈PX\in\mathcal{P} let H[X]:=(X,E[X])H[X]:=(X,E[X]) be the subhypergraph of edges contained in XX. Since r(E[X])≤∣X∣−1r(E[X])\le|X|-1 for each X∈PX\in\mathcal{P}, the sets E[X]E[X] contribute at most ∑X∈P(∣X∣−1)=v−∣P∣\sum_{X\in\mathcal{P}}(|X|-1)=v-|\mathcal{P}| to the rank, and each edge in δH(P)\delta_H(\mathcal{P}) contributes at most one. Equality implies that r(E[X])=∣X∣−1r(E[X])=|X|-1 for every X∈PX\in\mathcal{P}, every edge in δH(P)\delta_H(\mathcal{P}) is a coloop, and MM is the direct sum of these coloops and the restrictions M∣E[X]=M1,1(H[X])M|E[X]=M_{1,1}(H[X]) with E[X]≠∅E[X]\ne\varnothing. Each such H[X]H[X] has ∣X∣≥2|X|\ge2 and hence τ(H[X])≥1\tau(H[X])\ge1, so ρ(M1,1(H[X]))≤s\rho(M_{1,1}(H[X]))\le s by the first case, while each coloop has cogirth–strength ratio 11. Hence, Lemma 1 gives ρ(M)≤s.\rho(M)\le s.

For M1,0M_{1,0}, the bound follows from the transversal-matroid rank formula.

Proposition 2. If HH has edge size at most ss, then ρ(M1,0(H))≤s\rho(M_{1,0}(H))\le s.

Proof. Write M:=M1,0(H)M:=M_{1,0}(H) and V:=V(E)V:=V(E). The defect form of Hall’s theorem gives the standard transversal-matroid rank formula rM(A)=min⁡Y⊆A(∣A∖Y∣+∣V(Y)∣)r_M(A)=\min_{Y\subseteq A}(|A\setminus Y|+|V(Y)|) [27 Theorem 22.2]. Let Y0Y_0 attain the minimum for A=EA=E. Then rM(Y0)=∣V(Y0)∣r_M(Y_0)=|V(Y_0)|, otherwise some subset Y′⊆Y0Y'\subseteq Y_0 would yield a smaller value in the rank formula for EE. Hence r(M)=rM(Y0)+∣E∖Y0∣r(M)=r_M(Y_0)+|E\setminus Y_0|, so every element of E∖Y0E \setminus Y_0 is a coloop. If such an element exists, then λ(M)=σ(M)=1\lambda(M) = \sigma(M) = 1. We may therefore assume Y0=EY_0 = E and r(M)=∣V∣=:vr(M) = |V| =: v.

Take A⊆EA \subseteq E with rM(A)<vr_M(A) < v, and let Y⊆AY \subseteq A attain the minimum in the rank formula for AA. Put U:=V∖V(Y)U := V \setminus V(Y). Then v−rM(A)=∣U∣−∣A∖Y∣>0v - r_M(A) = |U| - |A \setminus Y| > 0. Applying the rank formula for EE to YY gives ∣E∖A∣≥v−rM(A)|E \setminus A| \ge v - r_M(A). Deleting all edges incident to any vertex in UU reduces the rank, so λ(M)\lambda(M) is at most the minimum number of edges incident to a vertex in UU. Since no edge of YY meets UU, and each edge of E∖YE \setminus Y meets at most ss vertices of UU, averaging gives

λ(M)≤s∣E∖Y∣∣U∣=s(∣E∖A∣+∣A∖Y∣)v−rM(A)+∣A∖Y∣≤s∣E∖A∣v−rM(A).\lambda(M) \le\frac{s|E \setminus Y|}{|U|} = \frac{s(|E \setminus A| + |A \setminus Y|)}{v - r_M(A) + |A \setminus Y|} \le\frac{s|E \setminus A|}{v - r_M(A)}.

where the last inequality follows from ∣E∖A∣≥v−rM(A)|E \setminus A| \ge v - r_M(A). Minimizing over such AA proves the proposition.

Propositions 1 and 2, together with (3) and Theorem 3, prove the upper bound ρ(Mk,ℓ(H))≤ks\rho(M_{k,\ell}(H)) \le ks in Theorem 4. We defer the matching lower bound to Appendix § 7: the complete ss-uniform hypergraphs Kv(s)K_v^{(s)} satisfy ρ(Mk,ℓ(Kv(s)))→ks\rho(M_{k,\ell}(K_v^{(s)})) \to ks as v→∞v \to\infty. Adding p−1p - 1 vertex-disjoint single-edge components to Kv(s)K_v^{(s)}, which contribute p−1p - 1 coloops, yields count matroids of hypergraphs with edge size at most ss whose rank-pp integrality gap λp/λp∗\lambda_p/\lambda_p^* also tends to ksks. Hence the LP gap bound ksks is sharp for every fixed pp.

Although our unweighted analysis does not generalize directly to the weighted case, it is natural to ask whether a bound independent of the weights still holds for all lower-range count matroids of bounded edge size. However, no such bound exists. In fact, the weighted cogirth–strength ratio, and hence the weighted integrality gap of (1), is unbounded even for (2,2)(2,2)-count matroids of simple graphs, whose bases are disjoint unions of two spanning trees.

For any integer q≥2q \ge2, form a simple graph GG from a grid with 2q2q rows and qq columns C1,…,CqC_1, \ldots, C_q by adding a vertex zz adjacent to both ends of every row. Give the 2q2q edges between zz and CqC_q weight 1 and call them light; give all other edges weight q+1q + 1 and call them heavy. We claim that the heavy edges together with any qq light edges decompose into two edge-disjoint spanning trees. Indeed, color the horizontal edges and the 2q2q edges between zz and C1C_1 red, and color the vertical edges blue; this partitions the heavy edges into a red spanning tree of size 2q22q^2 and a blue forest of size 2q2−q2q^2 - q with components z,C1,…,Cqz, C_1, \ldots, C_q. Adding any qq light edges to the red tree creates qq edge-disjoint cycles, each formed by zz and one chosen row. Assign these qq rows bijectively to C1,…,CqC_1, \ldots, C_q, and in the row assigned to CjC_j, recolor blue the red edge entering CjC_j from Cj−1C_{j-1} (or from zz if j=1j = 1). This breaks each red cycle while linking the blue components along zz, C1,…,CqC_1,\ldots,C_q into a spanning tree, proving the claim. Figure 1 illustrates the construction and the decomposition for q=2q=2.

Figure 1. The construction for q=2q = 2, with columns C1C_1, C2C_2 from left to right. Selecting the light edges in the first and third rows gives two edge-disjoint spanning trees TredT_{\mathrm{red}} and TblueT_{\mathrm{blue}}, whose union consists of all heavy edges and the two selected light edges.

Thus the heavy edges plus any qq light edges form a base of M:=M2,2(G)M := M_{2,2}(G), so r(M)=4q2r(M)=4q^2, and since there are 4q2−q4q^2-q heavy edges, every base uses at least qq light edges. Hence λw(M)=q+1\lambda_w(M)=q+1. Meanwhile, since every base uses at least qq of the 2q2q light edges, σw(M)≤2\sigma_w(M)\leq2, and splitting the light edges into two sets of size qq gives two bases within capacity ww, so σw(M)=2\sigma_w(M)=2 and ρwwt(M)=(q+1)/2\rho^{\mathrm{wt}}_w(M)=(q+1)/2.

Quasi-graphic matroids

Quasi-graphic matroids include all frame and lifted-graphic matroids [3]. In particular, for a graph GG, both the graphic matroid M1,1(G)M_{1,1}(G) and the bicircular matroid M1,0(G)M_{1,0}(G) are quasi-graphic. We use the tripartition description of Bowler, Funk, and Slilaty [3].

Let GG be a graph. A theta subgraph of GG consists of two distinct vertices together with three internally disjoint paths between them. A proper tripartition of the cycles of GG is a partition (B,L,F)(\mathcal{B},\mathcal{L},\mathcal{F}) of its cycles into balanced, lift-type, and frame-type cycles such that

  • no theta subgraph has exactly two of its three cycles in B\mathcal{B}, and

  • every cycle in L\mathcal{L} shares a vertex with every cycle in F\mathcal{F}.

A subgraph is balanced if all its cycles lie in B\mathcal{B}; in particular, an acyclic subgraph is balanced. For S⊆E(G)S\subseteq E(G), consider the spanning subgraph (V(G),S)(V(G),S). Let c(S)c(S) be its number of components, let b(S)b(S) be its number of balanced components, counting isolated vertices, and let η(S)=1\eta(S)=1 if SS contains a cycle in L\mathcal{L} and η(S)=0\eta(S)=0 otherwise.

The associated quasi-graphic matroid has rank function [3 Lemma 2.6]

r(S)={∣V(G)∣−b(S),if S contains a cycle in F,∣V(G)∣−c(S)+η(S),otherwise.r(S)= \begin{cases} |V(G)|-b(S), & \text{if } S \text{ contains a cycle in } \mathcal{F},\\ |V(G)|-c(S)+\eta(S), & \text{otherwise.} \end{cases}

Theorem 5. Every quasi-graphic matroid MM satisfies ρwt(M)≤2\rho^{\mathrm{wt}}(M)\leq2.

Proof. Fix weights w:E(M)→R≥0w:E(M)\to\mathbb{R}_{\geq0} with σw(M)>0\sigma_w(M)>0. By Lemma 1 we may assume that MM is connected. If MM is graphic, Nash–Williams–Tutte [24, 30] gives the bound directly. Otherwise, the connected-framework reduction of Bowler, Funk, and Slilaty [3] gives a connected graph G=(V,E)G=(V,E) and a proper tripartition representing MM. Its framework contains an unbalanced cycle, so r(E)=∣V∣r(E)=|V|. Put r:=r(E)r:=r(E) and λw:=λw(M)\lambda_w:=\lambda_w(M).

We prove that 2w(E∖S)≥hλw2w(E\setminus S)\geq h\lambda_w for every S⊆ES\subseteq E with h:=r−r(S)>0h:=r-r(S)>0. Taking the minimum of w(E∖S)/hw(E\setminus S)/h over SS then gives σw(M)≥λw(M)/2\sigma_w(M)\geq\lambda_w(M)/2.

For X⊆VX\subseteq V, let E[X]E[X] be the edges with both endpoints in XX, let S[X]:=S∩E[X]S[X]:=S\cap E[X], and let δ(X)\delta(X) be the edges with exactly one endpoint in XX. Let V1,…,VqV_1,\ldots,V_q be the vertex sets of the components of (V,S)(V,S). For each component set Ci:=(E[Vi]∖S[Vi])∪δ(Vi)⊆E∖SC_i:=(E[V_i]\setminus S[V_i])\cup\delta(V_i)\subseteq E\setminus S. Each edge of E∖SE\setminus S lies in at most two of these sets. An edge within one component, including a loop, lies in one CiC_i, while an edge joining two components lies in two.

Deleting CiC_i leaves ViV_i as a separated component carrying exactly S[Vi]S[V_i]. If this component is balanced, the rank drops: a surviving frame-type cycle makes the first line of the rank formula at most ∣V∣−1|V|-1, and otherwise the second line gives the same bound. In the latter case there are at least two components when Vi⊊VV_i\subsetneq V, while Vi=VV_i=V leaves a connected balanced graph of rank ∣V∣−1|V|-1.

Suppose SS contains no frame-type cycle and S[Vi]S[V_i] is unbalanced. It contains a lift-type cycle, which meets every frame-type cycle. Deleting CiC_i therefore destroys all frame-type cycles: none remains inside ViV_i, outside it, or across its boundary. Moreover, Vi⊊VV_i\subsetneq V, since otherwise SS would

::: have full rank. The surviving graph has at least two components, so the second line of the rank formula gives rank at most ∣V∣−1|V|-1.

If SS contains a frame-type cycle, charge its balanced components, whose number is h=b(S)h=b(S). Otherwise charge all qq components, where h=q−η(S)≤qh=q-\eta(S)\le q. Every charged CiC_i contains a cocircuit.

In all cases, at least hh components are charged, and each charged CiC_i has weight at least λw\lambda w. The multiplicity bound gives

hλw≤∑i chargedw(Ci)≤2w(E∖S).h\lambda w \le\sum_{i\ {\rm charged}} w(C_i) \le2w(E\setminus S).

as required.

The constant 2 is asymptotically sharp already for graphic matroids: the graphic matroid MM of KvK_v has λ(M)=v−1\lambda(M)=v-1 and σ(M)=v/2\sigma(M)=v/2, so ρ(M)=2−2/v→2\rho(M)=2-2/v\to2.

The quasi-graphic rank formula remains valid after deleting edges, so quasi-graphic matroids form a deletion-closed class. With Theorem 5, Theorem 1 and Theorem 2 give a 2-approximation and an exact n3p+O(1)n^{3p+O(1)}-time algorithm for weighted rank-pp reduction.

Acknowledgements Supported by the National Natural Science Foundation of China under grant 62372093 and by the CCF-Huawei Populus Grove Fund – Theoretical Computer Science Special Project CCF-HuaweiLK2025003.

We thank Benjamin Moseley for hosting Chao at the CMU Tepper School of Business, where part of this work was carried out.

AI disclosure The quasi-graphic result in § 6 was discovered by Fable 5, and the manuscript was prepared with assistance from AI tools. The authors take full responsibility for the correctness and content of the paper, including material generated with AI assistance.

Sharpness for lower-range count matroids

Throughout this appendix, fix integers k≥1k \ge1 and 0≤ℓ≤k0 \le\ell\le k. For a hypergraph H=(V,E)H = (V,E), A⊆EA \subseteq E, and X⊆VX \subseteq V, write A[X]:={e∈A:e⊆X}A[X] := \{e \in A : e \subseteq X\}. A vertex subpartition of HH is a collection X=(X1,…,Xq)\mathcal{X} = (X_1,\ldots,X_q) of pairwise disjoint nonempty subsets of VV, including the empty collection (q=0q = 0).

Lemma 3. Let H=(V,E)H = (V,E) be a hypergraph such that M:=Mk,ℓ(H)M := M_{k,\ell}(H) is loopless. For every A⊆EA \subseteq E,

rM(A)=min⁡X=(X1,…,Xq)(∣A∖⋃i=1qA[Xi]∣+∑i=1q(k∣Xi∣−ℓ))r_M(A) = \min_{\mathcal{X}=(X_1,\ldots,X_q)} \left(\left|A \setminus\bigcup_{i=1}^{q} A[X_i]\right| + \sum_{i=1}^{q}(k|X_i|-\ell)\right)

where X\mathcal{X} ranges over all vertex subpartitions of HH.

Proof. By the count-matroid rank formula [10 Section 13.5.2],

rM(A)=min⁡(Y1,…,Yp)(∣A∖⋃j=1pYj∣+∑j=1p(k∣V(Yj)∣−ℓ)).r_M(A) = \min_{(Y_1,\ldots,Y_p)} \left(\left|A \setminus\bigcup_{j=1}^{p} Y_j\right| + \sum_{j=1}^{p}(k|V(Y_j)|-\ell)\right).

where (Y1,…,Yp)(Y_1,\ldots,Y_p) ranges over collections of pairwise disjoint nonempty subsets of AA, including the empty collection. Starting from a minimizing collection (Y1,…,Yp)(Y_1,\ldots,Y_p), merging any two parts with V(Yi)∩V(Yj)≠∅V(Y_i)\cap V(Y_j) \ne\varnothing into Yi∪YjY_i \cup Y_j leaves A∖⋃tYtA \setminus\bigcup_t Y_t unchanged and changes ∑t(k∣V(Yt)∣−ℓ)\sum_t(k|V(Y_t)|-\ell) by ℓ−k∣V(Yi)∩V(Yj)∣≤ℓ−k≤0\ell-k|V(Y_i)\cap V(Y_j)| \le\ell-k \le0. Repeating until the supports Xi:=V(Yi)X_i := V(Y_i) are pairwise disjoint produces a vertex subpartition X=(X1,…,Xq)\mathcal{X} = (X_1,\ldots,X_q). Each XiX_i is nonempty since MM is loopless. Since Yi⊆A[Xi]Y_i \subseteq A[X_i] for each ii, we have ∣A∖⋃iA[Xi]∣≤∣A∖⋃iYi∣\left|A \setminus\bigcup_i A[X_i]\right| \le\left|A \setminus\bigcup_i Y_i\right|, so the value of X\mathcal{X} is at most rM(A)r_M(A).

Conversely, let I⊆AI \subseteq A be independent in MM and let X=(X1,…,Xq)\mathcal{X} = (X_1,\ldots,X_q) be a vertex subpartition. Since MM is loopless, every edge of II is nonempty, so I[X1],…,I[Xq]I[X_1],\ldots,I[X_q] are pairwise disjoint. Moreover, ∣I[Xi]∣≤k∣Xi∣−ℓ|I[X_i]| \le k|X_i|-\ell for every ii: this holds by independence of II when I[Xi]≠∅I[X_i] \ne\varnothing, and because k∣Xi∣−ℓ≥k−ℓ≥0k|X_i|-\ell\ge k-\ell\ge0 when I[Xi]=∅I[X_i] = \varnothing. Therefore

∣I∣=∣I∖⋃i=1qI[Xi]∣+∑i=1q∣I[Xi]∣≤∣A∖⋃i=1qA[Xi]∣+∑i=1q(k∣Xi∣−ℓ),|I| = \left|I \setminus\bigcup_{i=1}^{q} I[X_i]\right| + \sum_{i=1}^{q}|I[X_i]| \le\left|A \setminus\bigcup_{i=1}^{q} A[X_i]\right| + \sum_{i=1}^{q}(k|X_i|-\ell),

and taking the maximum over II gives the reverse inequality.

Proposition 3. For s≥3s \ge3, ρ(Mk,ℓ(Kv(s)))→ks\rho(M_{k,\ell}(K_v^{(s)})) \to ks as v→∞v \to\infty.

Proof. Write M:=Mk,ℓ(Kv(s))M := M_{k,\ell}(K_v^{(s)}), and put m:=(vs)m := \binom{v}{s}, R:=kv−ℓR := kv-\ell, Δ:=(v−1s−1)\Delta:= \binom{v-1}{s-1}, and μ:=Δ−kv\mu:= \Delta-kv. We prove, for all sufficiently large vv, that r(M)=Rr(M)=R, Δ−kv<λ(M)≤Δ\Delta-kv<\lambda(M)\le\Delta, and σ(M)=m/R\sigma(M)=m/R.

For a nonempty vertex subpartition X=(X1,…,Xq)\mathcal{X}=(X_1,\ldots,X_q) other than {V}\{V\}, put u:=v−∑i=1q∣Xi∣u:=v-\sum_{i=1}^q|X_i| and c:=m−∑i=1q(∣Xi∣s)c:=m-\sum_{i=1}^q\binom{|X_i|}{s}. Since the sets XiX_i are pairwise disjoint and nonempty, and X≠{V}\mathcal{X}\ne\{V\}, discrete convexity of t↦(ts)t\mapsto\binom{t}{s} yields ∑i=1q(∣Xi∣s)≤(v−1s)\sum_{i=1}^q\binom{|X_i|}{s}\le\binom{v-1}{s}. Indeed, the sum is maximized by concentrating the vertices into as few parts as possible, with at least two nonempty parts. Consequently, c≥(vs)−(v−1s)=(v−1s−1)=Δc\ge\binom{v}{s}-\binom{v-1}{s}=\binom{v-1}{s-1}=\Delta. Moreover, since ℓ≤k\ell\le k and ∑i∣Xi∣≥q\sum_i|X_i|\ge q, we have ku+ℓ(q−1)≤k(u+q−1)=k(v−∑i∣Xi∣+q−1)≤k(v−1)ku+\ell(q-1)\le k(u+q-1)=k\left(v-\sum_i|X_i|+q-1\right)\le k(v-1). By Lemma 3, the corresponding rank certificate has value c+∑i=1q(k∣Xi∣−ℓ)=R+c−ku−ℓ(q−1)≥R+Δ−k(v−1)≥R+μc+\sum_{i=1}^q(k|X_i|-\ell)=R+c-ku-\ell(q-1)\ge R+\Delta-k(v-1)\ge R+\mu. The empty certificate has value mm, which also satisfies m≥R+μm\ge R+\mu, since m−(R+μ)=m−Δ+ℓ=(v−1s)+ℓ≥0m-(R+\mu)=m-\Delta+\ell=\binom{v-1}{s}+\ell\ge0.

Choose vv large enough that μ≥0\mu\ge0. The full-block certificate {V}\{V\} has value RR, proving r(M)=Rr(M)=R. Deleting at most μ\mu edges decreases any other certificate by at most μ\mu, while the full-block value stays RR. Thus λ(M)>μ\lambda(M)>\mu. Deleting the Δ\Delta edges at one vertex leaves rank at most k(v−1)−ℓ<Rk(v-1)-\ell<R, giving the upper bound.

Averaging a base under the vertex permutations gives a fractional base packing of total weight m/Rm/R, and the empty flat gives the reverse inequality. Since Δ/m=s/v\Delta/m=s/v and kv/Δ→0kv/\Delta\to0 for s≥3s\ge3, the ratio tends to ksks.

For the graph lower bound, take v>2kv>2k and put M:=Mk,ℓ(Kv)M:=M_{k,\ell}(K_v). If D⊆E(Kv)D\subseteq E(K_v) has ∣D∣<v−2k|D|<v-2k, every nontrivial cut of Kv−DK_v-D has size at least v−1−∣D∣≥2kv-1-|D|\ge2k. Nash–Williams–Tutte [24, 30] gives kk edge-disjoint spanning trees. Minimum degree at least 2k2k gives at least kvkv edges, leaving at least kk edges outside these trees. Add one distinct unused edge to each of k−ℓk-\ell trees. The resulting ℓ\ell trees and k−ℓk-\ell spanning unicyclic graphs form an independent set of size kv−ℓkv-\ell by (3). Thus r(M)=kv−ℓr(M)=kv-\ell and λ(M)≥v−2k\lambda(M)\ge v-2k. Since the empty flat gives σ(M)≤(v2)/(kv−ℓ)\sigma(M)\le\binom{v}{2}/(kv-\ell),

ρ(M)≥(v−2k)(kv−ℓ)(v2)=2k−O(1/v).\rho(M)\ge\frac{(v-2k)(kv-\ell)}{\binom{v}{2}}=2k-O(1/v).

For s≥3s\ge3, Proposition 3 gives the lower bound ksks.

The LP gap bound ksks is sharp for every fixed pp. Let MvM_v be the complete-uniform examples above, using complete graphs when s=2s=2, and add p−1p-1 coloops to obtain NvN_v. Adding vertex-disjoint single-edge components realizes NvN_v as the count matroid of a hypergraph with edge size at most ss. Averaging a base under vertex permutations gives σ(Mv)=∣E(Mv)∣/r(Mv)→∞\sigma(M_v)=|E(M_v)|/r(M_v)\to\infty, while ρ(Mv)→ks\rho(M_v)\to ks. Every rank-pp reducing set in NvN_v lowers the rank of MvM_v, and deleting all added coloops together with a minimum cocircuit is feasible. Hence

λ(Mv)≤λp(Nv)≤λ(Mv)+p−1.\lambda(M_v)\le\lambda_p(N_v)\le\lambda(M_v)+p-1.

Also λp∗(Nv)=σ(Mv)+p−1\lambda_p^*(N_v)=\sigma(M_v)+p-1. Indeed, assigning one to the coloops and using an optimal rank-one solution on MvM_v proves the upper bound. If a feasible solution assigns total t≤p−1t\le p-1 to the coloops, its other coordinates meet each base of MvM_v to extent at least p−tp-t. Its total cost is therefore at least (p−t)σ(Mv)+t≥σ(Mv)+p−1(p-t)\sigma(M_v)+t\ge\sigma(M_v)+p-1, since σ(Mv)≥1\sigma(M_v)\ge1. Dividing the displayed bounds by σ(Mv)+p−1\sigma(M_v)+p-1 proves that λp(Nv)/λp∗(Nv)→ks\lambda_p(N_v)/\lambda_p^*(N_v)\to ks.

References

  1. [1]Robert F. Bailey, Mike Newman, and Brett Stevens. A note on packing spanning trees in graphs and bases in matroids. Australas. J. Combin., 59:24–38, 2014.
  2. [2]Mourad Baïou and Francisco Barahona. Packing hypertrees and the k-cut problem in hypergraphs. In Learning and Intelligent Optimization, volume 13621 of Lecture Notes in Computer Science, pages 521–534, Cham, 2022. Springer International Publishing.DOI
  3. [3]Nathan Bowler, Daryl Funk, and Daniel Slilaty. Describing quasi-graphic matroids, 2025. Version 4, incorporating corrections.
  4. [4]Paul A. Catlin, Jerrold W. Grossman, Arthur M. Hobbs, and Hong-Jian Lai. Fractional arboricity, strength, and principal partitions in graphs and matroids. Discrete Applied Mathematics, 40(3):285–302, 1992.DOI
  5. [5]Karthekeyan Chandrasekaran, Chandra Chekuri, and Weihao Zhu. Random deletion for circuits in regular matroids. arXiv:2610.33918, 2026.arxiv.org/abs/2610.33918
  6. [6]Chandra Chekuri, Kent Quanrud, and Chao Xu. LP Relaxation and Tree Packing for Minimum k-Cut. SIAM Journal on Discrete Mathematics, 34(2):1334–1353, 2020.DOI
  7. [7]Yu Cong, Chao Xu, and Yajie Zhao. Derandomizing Karger’s contraction algorithm for matroids. arXiv:2608.16298, 2026.arxiv.org/abs/2608.16298
  8. [8]Yu Cong, Chao Xu, and Yajie Zhao. Destroying rigidity in the plane. arXiv:2610.38396, 2026.arxiv.org/abs/2610.38396
  9. [9]Jack Edmonds. Lehman’s switching game and a theorem of Tutte and Nash-Williams. Journal of Research of the National Bureau of Standards, Section B: Mathematics and Mathematical Physics, 69B(1–2):73–77, 1965.
  10. [10]András Frank. Connections in Combinatorial Optimization. Oxford University Press, 2011.DOI
  11. [11]András Frank, Tamás Király, and Matthias Kriesell. On decomposing a hypergraph into k connected sub-hypergraphs. Discrete Applied Mathematics, 131(2):373–383, 2003.DOI
  12. [12]Takuro Fukunaga. Computing minimum multiway cuts in hypergraphs. Discrete Optimization, 10(4):371–382, 2013.DOI
  13. [13]Jim Geelen and Rohan Kapadia. Computing Girth and Cogirth in Perturbed Graphic Matroids. Combinatorica, 38(1):167–191, feb 2018.arxiv.org/abs/1504.07647
  14. [14]Olivier Goldschmidt and Dorit S. Hochbaum. A polynomial algorithm for the k-cut problem for fixed k. Mathematics of Operations Research, 19(1):24–37, 1994.DOI
  15. [15]Anupam Gupta, David G. Harris, Euiwoong Lee, and Jason Li. Optimal bounds for the k-cut problem. Journal of the ACM, 69(1):1–18, 2022.arxiv.org/abs/2005.08301
  16. [16]Anupam Gupta, Euiwoong Lee, and Jason Li. Faster exact and approximate algorithms for k-cut. In 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 113–123, 2018.arxiv.org/abs/1807.08144
  17. [17]Gwenaël Joret and Adrian Vetta. Reducing the rank of a matroid. Discrete Mathematics & Theoretical Computer Science, 17(2):143–156, sep 2015.
  18. [18]David R. Karger. Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 21–30, 1993.DOI
  19. [19]David R. Karger. Random sampling and greedy sparsification for matroid optimization problems. Mathematical Programming, 82(1-2):41–81, 1998.DOI
  20. [20]David R. Karger and Clifford Stein. A new approach to the minimum cut problem. Journal of the ACM, 43(4):601–640, 1996.DOI
  21. [21]Tamás Király. Computing the minimum cut in hypergraphic matroids. Technical Report QP-2009-05, Egerváry Research Group, Budapest, 2009. www.cs.elte.hu/egres.
  22. [22]Jason Li. Faster minimum k-cut of a simple graph. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1056–1077. IEEE, 2019.arxiv.org/abs/1910.02665
  23. [23]H. Narayanan, Subir K. Roy, and Sachin B. Patkar. Approximation algorithms for min-k-overlap problems using the principal lattice of partitions approach. Journal of Algorithms, 21(2):306–330, 1996.
  24. [24]C. St. J. A. Nash-Williams. Edge-disjoint spanning trees of finite graphs. Journal of the London Mathematical Society, s1-36(1):445–450, 1961.
  25. [25]James G. Oxley. Matroid Theory. Oxford graduate texts in mathematics. Oxford University Press, 2006.
  26. [26]Huzur Saran and Vijay V. Vazirani. Finding k cuts within twice the optimal. SIAM Journal on Computing, 24(1):101–108, 1995.
  27. [27]Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency. Number 24 in Algorithms and combinatorics. Springer, Berlin Heidelberg, 2003.
  28. [28]Ileana Streinu and Louis Theran. Sparse hypergraphs and pebble game algorithms. European Journal of Combinatorics, 30(8):1944–1964, 2009.arxiv.org/abs/math/0703921
  29. [29]Mikkel Thorup. Minimum k-way cuts via deterministic greedy tree packing. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 159–166, 2008.DOI
  30. [30]W. T. Tutte. On the problem of decomposing a graph into n connected factors. Journal of the London Mathematical Society, s1-36(1):221–230, 1961.DOI

Paper details

vlnc:W_2c4nf2mm
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents