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.
Let be a matroid without coloop. Then one has where is the minimum number of circuits whose union is , is the number of connected components in , is the corank and is the max number of disjoint circuits.
The left hand side is called the circuit covering defect and the right hand side is called the circuit packing defect. I guess the name “covering defect” comes from the fact that is the gap between the circuit covering number and a lowerbound . 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 as the max size of such that for all circuit and write as the minimum size of such that for all circuit .
2 Complexity
Computing the corank and the component number is easy. What about and ?
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 and 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.
Given a matroid and a non-negative integral weight function , decide if there is a multiset of circuits of such that each element in is covered by at least 1 and at most circuits in the multiset.
[4] studied a related (and seemingly simplier) optimization variant. How many circuits can we pack with element capacity ?
Clearly the linear relaxation of and of are LP dual of each other and have the same optimum. For what class of matroids do we have equality for any weight function ?
When this is relatively simple. First we can assume that contains no coloop since coloops won’t appear in any circuit. Suppose that there are two circuits whose intersection is non-empty. Let be the smallest weight of elements in respectively. It follows by definition that and . The max number of circuits we can pack in the matroid is . Now we further assume that . The minimum weight of elements hitting every circuit is not necessarily , since by the circuit axiom there must another circuit for any which won’t be hit if we are selecting element in . Thus for the case of , any matroid satisfying has no intersecting circuits.
The characterization of matroids satisfying is the following theorem [4].

Their proof is also based on LP. In fact they prove the following theorem.
Let be a matroid. The following statements are equivalent:
- does not contain or as a minor;
- the linear system is TDI;
- the polytope is integral.
is easy. To show they prove that if satisfies 3 then so do its minors and none of the matroids in 1 satisfies 3. The hard part is proving , for which they use the following two lemmas.
If satisfies 1, then for some graph that contains neither the planar dual of nor of as a minor.
A matroid is regular iff it has no minor isomorphic to . Then 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 and . (see Corollary 10.4.3 in Oxley’s Matroid Theory book 2nd edition)
If a graph contains neither the planar dual of nor of as a minor, then 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 nor that of as a minor using -sum and then prove that summing operations preserves the TDI property.
The -sum theorem looks like this. Let and be the planar dual of graph and respectively.
A simple graph has no minors and iff can be obtained by repeatedly taking -sums starting from some small graphs and from some cyclically 3-connected graphs with no minors and .
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 be a rational matrix and be an integral vector. For any rational we have the following inequalities:
If we have equality on the last two for all integral , then then all five optima are equal for each integral vector . It suffices to require that the last two optimum are equal for each integral .
The rational system is TDI, iff is finite and is attained by integral for each integral such that is finite.
This is exactly the case of in the characterization of matroids with .
The above theorem on TDI reduces proving that is TDI to proving that has an integral optimal solution for all nonnegative integral
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 has an integral optimal solution. They further characterizes good graphs using cuts.
Let be a collection(multiset) of cuts in . is truncatable if there is another collection of cuts in , such that
- ,
- Let for a collection be the number of elements in containing . for all
A graph 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 . As noted before and in their paper, matroids that satisfy must be direct sums of circuits (if there is no coloop). The 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 Is this problem interesting or is there any existing paper?