Matroid circuit packing and covering

Posted on June 15, 2025 by Yu Cong, with the help of Kangyi Tian
Tags: , ,

In the previous post, we mainly focus on the algorithmic part of integral and fractional base packing and base covering. In this post we consider packing and covering of matroid circuits.

1 Packing/Covering Defect

Seymour [1] proved the following theorem.
Theorem1

Let M=(E,I)M=(E,I) be a matroid without coloop. Then one has θ(M)−κ(M)≤r*(M)−ν(M),\theta(M)-\kappa(M)\leq r^*(M)-\nu(M), where θ(M)\theta(M) is the minimum number of circuits whose union is EE, κ(M)\kappa(M) is the number of connected components in MM, r*r^* is the corank and ν(M)\nu(M) is the max number of disjoint circuits.

The left hand side θ(M)−κ(M)\theta(M)-\kappa(M) is called the circuit covering defect and the right hand side r*(M)−ν(M)r^*(M)-\nu(M) is called the circuit packing defect. I guess the name “covering defect” comes from the fact that θ(M)−κ(M)\theta(M)-\kappa(M) is the gap between the circuit covering number and a lowerbound κ(M)\kappa(M). κ(M)≤θ(M)\kappa(M)\leq \theta(M) since there is no circuit containing two elements in different components. The packing defect is the set-point dual of the covering version. To see the duality, one can write κ(M)\kappa(M) as the max size of X⊂EX\subset E such that |C∩X|≤1|C\cap X|\leq 1 for all circuit CC and write r*(M)r^*(M) as the minimum size of X⊂EX\subset E such that |X∩C|≥1|X\cap C|\geq 1 for all circuit CC.

2 Complexity

Computing the corank r*r^* and the component number κ(M)\kappa(M) is easy. What about θ(M)\theta(M) and ν(M)\nu(M)?

The problem of determining if a sparse split graph (a special case of chordal graphs) can have its edges partitioned into edge-disjoint triangles is NP-complete [2]. So finding θ(M)\theta(M) and ν(M)\nu(M) is NP-hard even for some special graphic matroids.

3 Cycle Double Cover

Cycle double cover conjecture is a famous unsolved problem posed by W. T. Tutte, Itai and Rodeh, George Szekeres and Paul Seymour. The cycle double cover conjecture asks whether every bridgeless undirected graph has a collection of cycles such that each edge of the graph is contained in exactly two of the cycles.

[3] is a nice survey. However, there is little discussion about (even simplier version of) circuit double cover on some special case of matroids. For example, this question on math.sx is a relaxation of faithful CDC on matroids.
Problem2Not so faithful circuit cover

Given a matroid M=(E,ℐ)M=(E,\mathcal I) and a non-negative integral weight function w:E→ℤ≥0w:E\to \mathbb{Z}_{\geq 0}, decide if there is a multiset of circuits of MM such that each element in EE is covered by at least 1 and at most w(e)w(e) circuits in the multiset.

[4] studied a related (and seemingly simplier) optimization variant. How many circuits can we pack with element capacity kw(e)k w(e)?

νk,w=max∑CxCs.t.∑C:e∈CxC≤kw(e)∀e∈ExC∈ℤ≥0 \begin{aligned} \nu_{k,w}=\max& & \sum_C x_C& & &\\ s.t.& & \sum_{C:e\in C} x_C &\leq k w(e) & &\forall e\in E\\ & & x_C &\in \mathbb{Z}_{\geq 0} \end{aligned}

τk,w=min∑ew(e)yes.t.∑e∈Cye≥k∀ circuit Cye∈ℤ≥0 \begin{aligned} \tau_{k,w}=\min& & \sum_e w(e)&y_e & &\\ s.t.& & \sum_{e\in C} y_e &\geq k & &\forall \text{ circuit $C$}\\ & & y_e &\in \mathbb{Z}_{\geq 0} \end{aligned}

Clearly the linear relaxation of νk,w\nu_{k,w} and of τk,w\tau_{k,w} are LP dual of each other and have the same optimum. For what class of matroids do we have equality νk,w=τk,w\nu_{k,w}=\tau_{k,w} for any weight function ww?

When k=1k=1 this is relatively simple. First we can assume that MM contains no coloop since coloops won’t appear in any circuit. Suppose that there are two circuits C1,C2C_1,C_2 whose intersection is non-empty. Let a,b,ca,b,c be the smallest weight of elements in C1,C2,C1∩C2C_1,C_2, C_1\cap C_2 respectively. It follows by definition that a≤ca\leq c and b≤cb\leq c. The max number of circuits we can pack in the matroid M|C1∪C2M|_{C_1\cup C_2} is min⁡(a+b,c)\min(a+b,c). Now we further assume that a,b≤c≤a+ba,b\leq c\leq a+b. The minimum weight of elements hitting every circuit is not necessarily cc, since by the circuit axiom there must another circuit C′∈C1∪C2−eC'\in C_1\cup C_2-e for any e∈C1∩C2e\in C_1\cap C_2 which won’t be hit if we are selecting element in C1∩C2C_1\cap C_2. Thus for the case of k=1k=1, any matroid satisfying ν1,w=τ1,w\nu_{1,w}=\tau_{1,w} has no intersecting circuits.

The characterization of matroids satisfying ν2,w=τ2,w\nu_{2,w}=\tau_{2,w} is the following theorem [4].
Theorem3 A matroid satisfies ν2,w=τ2,w\nu_{2,w}=\tau_{2,w} iff none of its minor is isomorphic to U2,4,F7,F7*,M(K3,3),M(K5−)U_{2,4},F_7,F_7^*,M(K_{3,3}),M(K_5^-) or M(K)M(K), where K5−K_5^- is K5K_5 deleting an edge and KK is a special 4-node graph.
Graph K

Their proof is also based on LP. In fact they prove the following theorem.
Theorem4

Let MM be a matroid. The following statements are equivalent:
  1. MM does not contain U2,4,F7,F7*,M(K3,3),M(K5−)U_{2,4},F_7,F_7^*,M(K_{3,3}),M(K_5^-) or M(K)M(K) as a minor;
  2. the linear system {∑e∈Cye≥2∀C,ye≥0}\{ \sum_{e\in C} y_e \geq 2 \;\forall C, y_e\geq 0\} is TDI;
  3. the polytope {y:∑e∈Cye≥2∀C,ye≥0}\{y: \sum_{e\in C} y_e \geq 2 \;\forall C, y_e\geq 0\} is integral.

2→32\to 3 is easy. To show 3→13\to 1 they prove that if MM satisfies 3 then so do its minors and none of the matroids in 1 satisfies 3. The hard part is proving 1→21\to 2, for which they use the following two lemmas.
Lemma5

If MM satisfies 1, then M=M*(G)M=M^*(G) for some graph GG that contains neither the planar dual of KK nor of K5−K_5^- as a minor.
Proof

A matroid MM is regular iff it has no minor isomorphic to U2,4,F7,F7*U_{2,4},F_7,F_7^*. Then MM must be regular since it satisfies 1. The lemma then follows from the “excluded minor characterization of graphic matroids in regular matroids”. A regular matroid is cographic iff it has no minor isomorphic to M(K5)M(K_5) and M(K3,3)M(K_{3,3}). (see Corollary 10.4.3 in Oxley’s Matroid Theory book 2nd edition)
Lemma6

If a graph GG contains neither the planar dual of KK nor of K5−K_5^- as a minor, then M*(G)M^*(G) satisfies 2.

This is the hardest part and it takes a lot of work to prove it.

They first prove a complete characterization of grpahs that contain neither the planar dual of KK nor that of K5−K_5^- as a minor using 0,1,20,1,2-sum and then prove that summing operations preserves the TDI property.

The 0,1,20,1,2-sum theorem looks like this. Let K*K^* and PP be the planar dual of graph KK and K5−K_5^- respectively.
Theorem7informal, thm 3.1 in [4]

A simple graph GG has no minors PP and K*K^* iff GG can be obtained by repeatedly taking 0,1,20,1,2-sums starting from some small graphs and from some cyclically 3-connected graphs with no minors PP and K*K^*.

It remains to show that all the summand graphs in the above theorem have the TDI property.

some notes on TDI (cf. section 22.7 in [5])

Let AA be a rational matrix and bb be an integral vector. For any rational cc we have the following inequalities:

max⁡{cx|Ax≤b;x≥0;x integral}≤max⁡{cx|Ax≤b;x≥0}=min⁡{yb|yA≥c;y≥0}≤min⁡{yb|yA≥c;y≥0;y half-integral}≤min⁡{yb|yA≥c;y≥0;y integral} \begin{aligned} &\max \left\{ cx| Ax\leq b; x\geq 0; \text{$x$ integral} \right\} \\ \leq &\max \left\{ cx| Ax\leq b; x\geq 0 \right\}\\ = &\min \left\{ yb| yA\geq c; y\geq 0 \right\}\\ \leq &\min \left\{ yb| yA\geq c; y\geq 0; \text{$y$ half-integral} \right\}\\ \leq &\min \left\{ yb| yA\geq c; y\geq 0; \text{$y$ integral} \right\} \end{aligned}

If we have equality on the last two ≤\leq for all integral cc, then then all five optima are equal for each integral vector cc. It suffices to require that the last two optimum are equal for each integral cc.
Theorem8

The rational system Ax≤bAx\leq b is TDI, iff min⁡{yb|yA≥c;y≥0;y half-integral}\min \left\{ yb| yA\geq c; y\geq 0; \text{$y$ half-integral} \right\} is finite and is attained by integral yy for each integral cc such that min⁡{yb|yA≥c;y≥0}\min \left\{ yb| yA\geq c; y\geq 0 \right\} is finite.

This is exactly the case of k=2k=2 in the characterization of matroids with ν2,w=τ2,w\nu_{2,w}=\tau_{2,w}.

The above theorem on TDI reduces proving that {∑e∈Cye≥2∀C,ye≥0}\{ \sum_{e\in C} y_e \geq 2 \;\forall C, y_e\geq 0\} is TDI to proving that τ′=max⁡{∑CxC|∑C:e∈C12xe≥w(e)∀e,xC≥0, xC half-integral}\tau'=\max \{ \sum_C x_C |\sum_{C:e\in C} \frac{1}{2} x_e \geq w(e) \;\forall e, x_C\geq 0, \text{ $x_C$ half-integral}\} has an integral optimal solution for all nonnegative integral w.w.

Recall that it remains to prove that some cographic matroids have the above property. The set of circuits corresponds to cuts in graphs. A graph is good if its cographic matroid satisfies that τ′\tau' has an integral optimal solution. They further characterizes good graphs using cuts.

Let 𝒞\mathcal C be a collection(multiset) of cuts in GG. 𝒞\mathcal C is truncatable if there is another collection 𝒟\mathcal D of cuts in GG, such that
  1. |𝒟|≥|𝒞|/2|\mathcal D|\geq |\mathcal C|/2,
  2. Let dX(e)d_{X}(e) for a collection XX be the number of elements in XX containing ee. d𝒟(e)≤2⌊d𝒞(e)/4⌋d_{\mathcal D}(e)\leq 2 \left\lfloor d_{\mathcal C}(e)/4 \right\rfloor for all ee

A graph GG is truncatable if every collection of its cuts is truncatable. They shows that a graph is good if and only if it is truncatable. Then this becomes a graph theory problem. They provides some sufficient condition for graphs to be truncatable and manage to prove all the graphs we are interested in are good. (a 16-page long proof)

Ding and Zang’s work [4] characterizes matroids that satisfy ν2,w=τ2,w\nu_{2,w}=\tau_{2,w}. As noted before and in their paper, matroids that satisfy ν1,w=τ1,w\nu_{1,w}=\tau_{1,w} must be direct sums of circuits (if there is no coloop). The k=1k=1 result can be understood as finding matroids whose integral circuit packing number and integral circuit hitting set number are equal. One may wonder if people have studied similar things on matroid bases. There are lots of works (see refs in this paper) on homogeneous matroids which have the property that fractional base packing number (strength) equals to fractional base covering number (fractional arboricity or density). However, the analogous question for bases should be characterizing matroids with cogirth=⌊strength⌋.\text{cogirth}=\left\lfloor \text{strength} \right\rfloor. Is this problem interesting or is there any existing paper?

Updated on Aug 14th. Yes, there is existing paper characterizing matroids with λ=⌊σ⌋.\lambda=\left\lfloor \sigma \right\rfloor.

Let MM be a matroid with ⌊σ(M)⌋≥k\left\lfloor \sigma(M) \right\rfloor\geq k. We call MM kk-reducible if λ(M)=⌊σ(M)⌋=k\lambda(M)=\left\lfloor \sigma(M) \right\rfloor=k. Otherwise MM is kk-irreducible. Let C1*,…,Cℓ*C_1^*,\ldots,C_\ell^* be the set of minimum cocircuits of MM. Then the crux of MM, denoted χ(M)\chi(M), is defined to be χ(M)=M\⋃i=1ℓCi*. \chi(M)=M\setminus\bigcup_{i=1}^\ell C_i^*.

Let δ(M)\delta(M) be the number of connected components of χ(M)\chi(M). Assume that χ(M)\chi(M) has dd connected components K1,…,KdK_1,\ldots,K_d. For each minimum cocircuit Cj*C_j^* of MM, let νj\nu_j denote the largest subset of {K1,…,Kd}\left\{ K_1,\ldots,K_d \right\} such that the restriction of MM to Cj*∪(⋃K∈νjK)C_j^*\cup \left( \bigcup_{K\in \nu_j} K \right) is connected. Then the assembly hypergraph of MM , denoted ℋ(M)\mathcal H(M), is the non-uniform hypergraph whose vertices are labelled by the connected components K1,...,KdK_1, . . . , K_d, where the hyperedges are labelled by the cocircuits C1*,…,Cℓ*C_1^*,\ldots,C_\ell^*, and the vertices incident with Cj*C_j^* are precisely the members of νj\nu_j.
Theorem9Theorem 21 in [6]

Suppose that MM is a matroid for which ⌊σ(M)⌋=λ(M)=k\left\lfloor σ(M) \right\rfloor = λ(M) = k. Then we have the following.
  1. There exists a unique set of k-irreducible matroids ℳ={M1,...,Mm}\mathcal M= \{M_1, . . . , M_m\} (for some integer mm).
  2. There exists a unique rooted tree RR with mm leaves labelled by M1,...,MmM_1, . . . , M_m, such that the root is labelled by MM and each non-leaf labelled by KK has d=δ(K)d= δ(K) children, labelled by the connected components of χ(K)\chi(K).
  3. For each non-leaf, labelled by KK and its dd children labelled K1,...,KdK_1, . . . , K_d, there exists a unique assembly hypergraph with ℓ\ell hyperedges, and where ∑i=1dr(Ki)=r(K)−ℓ\sum_{i=1}^d r(K_i)=r(K)-\ell.

References

[1]
P.D. Seymour, Packing and covering with matroid circuits, Journal of Combinatorial Theory, Series B. 28 (1980) 237–242 10.1016/0095-8956(80)90067-2.
[2]
T. Feder, C. Subi, Packing Edge-Disjoint Triangles in Given Graphs, Weizmann Institute of Science, ECCC, 2012.
[3]
C.-Q. Zhang, Circuit double covers of graphs, in: Graph Theory, Springer International Publishing, Cham, 2016: pp. 273–291 10.1007/978-3-319-31940-7_16.
[4]
G. Ding, W. Zang, Packing circuits in matroids, Mathematical Programming. 119 (2009) 137–168 10.1007/s10107-007-0205-6.
[5]
A. Schrijver, Theory of linear and integer programming, Wiley, Chichester ; New York, 1986.
[6]
R.F. Bailey, M. Newman, B. Stevens, A note on packing spanning trees in graphs and bases in matroids, (2014).