Matroid base packing and covering

Posted on January 4, 2025 by Yu Cong
Tags: , ,

There are few text books in combinatorial optimization discussing topics in matroid base packing, while matroid base covering(matroid partition problem) is everywhere. Packing and covering of trees in graphs can be found in chapter 51 in [1].

1 Base packing & base covering

Problem1

Given a matroid M=(E,ℐ⁡)M=(E,\mathop{\mathrm{\mathcal I}}) and its bases ℬ\mathop{\mathrm{\mathcal B}}, find
  1. (minimum base covering) the min number of bases whose union is EE, and
  2. (maximum base packing) the max number of pairwise disjoint bases.

These problems can be formulated with the following integer programs, base packing: max∑B∈ℬxBs.t.∑B:e∈BxB≤1∀e∈ExB∈{0,1}∀ base B\begin{align*} \max& & \sum_{B\in\mathop{\mathrm{\mathcal B}}} x_B& & &\\ s.t.& & \sum_{B:e\in B} x_B &\leq 1 & &\forall e\in E\\ & & x_B&\in \left\{ 0,1 \right\} & &\forall \text{ base $B$} \end{align*}

base covering: min∑B∈ℬxBs.t.∑B:e∈BxB≥1∀e∈ExB∈{0,1}∀ base B\begin{align*} \min& & \sum_{B\in\mathop{\mathrm{\mathcal B}}} x_B& & &\\ s.t.& & \sum_{B:e\in B} x_B &\geq 1 & &\forall e\in E\\ & & x_B&\in \left\{ 0,1 \right\} & &\forall \text{ base $B$} \end{align*}

Integer programs are hard and these IPs have exponential number of variables. We consider the linear relaxations.

Actually these two problems are not hard on general matroids. Both of them can be solved in polynomial number of independence oracle calls.
  • matroid base covering = matroid partitioning ≈ matroid union. Let M=(E,ℐ⁡)M=(E,\mathop{\mathrm{\mathcal I}}) be the matroid. The minimum number of bases that cover the groundset is arg⁡minkrk(E)=|E|\arg\min\limits_k r_{k}(E)=|E|, where rk(⋅)r_{k}(\cdot) is the rank function of MkM^k.
  • matroid base packing ≈ matroid union. Maximum integral base packing number is arg⁡maxkrk(E)=kr(M)\arg\max\limits_k r_{k}(E)=kr(M).

Thus the integral version of these two problem is polynomial solvable (in terms of the number of oracle calls) since matroid union is tractable. We will discuss computing the fractional version later.

2 Matroid strength and density

We will talk about matroid strength and density and their relation with base packing and covering in this section. I think none of the results is new. You can find some of them in [2] and [3].

The fractional base covering number for graphic matroids are called fractional arboricity. It is known that the fractional arboricity α(G)\alpha(G) equals to max∅⊊X⊂E|X|r(X)\max\limits_{\emptyset \subsetneq X\subset E}\frac{|X|}{r(X)}. Define the density for a matroid MM as α(M)=max∅⊊X⊂E|X|r(X)\alpha(M)=\max\limits_{\emptyset \subsetneq X\subset E}\frac{|X|}{r(X)}. The name “density” comes from [2]. I use symbol α\alpha since density is a generalization of arboricity.

For the packing part consider the fractional version of Nash-Williams theorem,
Theorem2

The fractional spanning tree packing number of a connected graph G=(V,E)G=(V,E) equals to max⁡|E[𝒫]||𝒫|−1\max \frac{|E[\mathcal P]|}{|\mathcal P|-1}, where the maximum is taken among all partitions 𝒫\mathcal P of VV.

The fraction in above theorem can be rewrite as |E−F|r(E)−r(F)\frac{|E-F|}{r(E)-r(F)}, which only uses elements in the groundset and the rank function and thus can be generalized to non-graphic matroids. The maximum of this fraction, σ(M)=max⁡F⊂E|E−F|r(E)−r(F)\sigma(M)=\max_{F\subset E}\frac{|E-F|}{r(E)-r(F)} is called matroid strength.(The name also comes from [2].)

For the connections between density and strength, we have the following inequality,

α(M)=max⁡|X|r(X)≥|E|r(E)≥min⁡|E−F|r(E)−r(F)=σ(M). \alpha(M)=\max \frac{|X|}{r(X)} \geq \frac{|E|}{r(E)} \geq \min \frac{|E-F|}{r(E)-r(F)} =\sigma(M).
Theorem3

Maximum fractional base packing number is σ(M)\sigma(M).
Proof

The proof is similar to the graph strength proof for tree packing in [1]. Let B(M)B(M) be the base polytope of MM and Π\Pi be the powerset of EE. Consider the following linear programs, LP1=minlxs.t.x∈B(M)\begin{align*} LP1=\min& & lx& \\ s.t.& & x&\in B(M) \end{align*}

LP2=max∑F⊊EyE\F(r(E)−r(F))s.t.∑F⊊EyE\FχE\F≤ly∈ℝ+Π\begin{align*} LP2=\max& & \sum_{F\subsetneq E} y_{E\setminus F}(r(E)-r(F))& \\ s.t.& & \sum_{F\subsetneq E} y_{E\setminus F} \chi^{E\setminus F} & \leq l\\ & & y & \in \mathbb{R}^\Pi_+ \end{align*}

and the dual of LP2LP2, LP3=minlxs.t.xTχE\F≥r(E)−r(F)∀F⊊Ex∈ℝ+E\begin{align*} LP3=\min& & lx& & &\\ s.t.& & x^T\chi^{E\setminus F} &\geq r(E)-r(F) & &\forall F\subsetneq E\\ & & x&\in \mathbb{R}^E_+ & & \end{align*}

We first prove that the polyhedron in LP3LP3, Q={x|x≥0,xTχE\F≥r(E)−r(F)∀F⊊E}Q=\{ x | x\geq 0,x^T\chi^{E\setminus F} \geq r(E)-r(F) \quad \forall F\subsetneq E\} is the base polytope of MM. One can see that B(M)⊆QB(M)\subseteq Q. Now suppose QQ is larger than B(M)B(M), there must exists x∈Qx\in Q such that x(U)>r(U)x(U)>r(U) for some U⊆EU\subseteq E. Thus OPT⁡(LP3)>OPT⁡(LP1)\mathop{\mathrm{OPT}}(LP3)>\mathop{\mathrm{OPT}}(LP1). However, for the optimal solution xx to LP1LP1 and any feasible solution yy to LP2LP2 we have OPT⁡(LP1)≥∑F⊊EyE\FχE\F⋅x=∑F⊊EyE\F(∑e∈Exe−∑e∈Fxe)≥∑F⊊EyE\F(r(E)−r(F))=OPT⁡(LP3) \mathop{\mathrm{OPT}}(LP1)\geq \sum_{F\subsetneq E} y_{E\setminus F}\chi^{E\setminus F}\cdot x = \sum_{F\subsetneq E} y_{E\setminus F} \left(\sum_{e\in E}x_e-\sum_{e\in F}x_e\right)\geq \sum_{F\subsetneq E} y_{E\setminus F} \left(r(E)-r(F)\right)=\mathop{\mathrm{OPT}}(LP3) Hence Q=B(M)Q=B(M).

Recall that σ(M)=min⁡F⊊E|E\F|r(E)−r(F)\sigma(M)=\min_{F\subsetneq E}\frac{|E\setminus F|}{r(E)-r(F)}. Note that σ(M)≥1\sigma(M)\geq 1. σ(M)\sigma(M) can be interpreted as the largest λ>1\lambda>1 such that |E\F|≥λ(r(E)−r(F))|E\setminus F| \geq \lambda(r(E)-r(F)) holds for all F⊊EF\subsetneq E. Hence σ(M)=max⁡{λ|𝟏∈λB(M)}\sigma(M)=\max \{\lambda | \mathbf 1\in \lambda B(M)\} since Q=B(M)Q=B(M). For fixed λ\lambda, 𝟏∈λB(M)\mathbf 1 \in \lambda B(M) if and only if there exists λb≥0\lambda_b\geq 0 for all bases of MM such that ∑bλb=λ\sum_b \lambda_b=\lambda and ∑bλbχb≤1\sum_b \lambda_b \chi^b\leq 1. Hence this shows σ(M)\sigma(M) is exactly the base packing LP max⁡{∑bλb|∑bλbχb≤1,λb≥0∀b∈B}\max\{\sum_b{\lambda_b}| \sum_{b}\lambda_b\chi^b\leq 1,\lambda_b\geq 0\;\forall b\in B\}.

Note that this proof is a straightforward generalization of the tree packing theorem in [1], which is similar to the blocking polyhedra method described in [4].

2.1 Constructive proof

In [5] there is a constructive proof that recovers the optimal F⊂EF\subset E in σ(M)\sigma(M) from any optimal solution of hitting set LP(dual to base packing).

The idea is to show that any fraction solution yy to base hitting set can be converted to another solution y′y' such that y′(e)∈{0,c}y'(e)\in \left\{ 0,c \right\} for some global constant cc and ∑ew(e)y′(e)≤∑ew(e)y(e)\sum_e w(e)y'(e)\leq \sum_e w(e)y(e).

Define two sets P,P′∈ℝ|E|P, P'\in \mathbb{R}^{|E|}, P={y∈ℝ|E|:y(e)≥0∀e∈E;y(B)≥1∀ base B},P′={y∈P:∀e∈E,∃Be∈ℬs.t.e∈Be∧y(Be)=minB∈ℬy(B)}. \begin{aligned} P &=\left\{ y\in \mathbb{R}^{|E|}: y(e)\geq 0 \;\forall e\in E; y(B)\geq 1 \; \forall \text{ base B} \right\},\\ P' &=\left\{ y\in P: \forall e\in E, \exists B^e\in \mathcal B \; s.t. \; e\in B^e \land y(B^e)=\min_{B\in \mathcal B} y(B) \right\}. \end{aligned}

P′P' is contained in PP and every element is in a minimum base with respect to weights y:E→ℝy:E\to \mathbb{R}.
Proposition4

Let y∈Py\in P. There exists y′∈P′y'\in P' s.t. y(e)≥y′(e)y(e)\geq y'(e) for all ee.
Proof

The proof is contrustive. Let B={e1,…,er}B=\left\{ e_1,\ldots, e_r \right\} be a minimum weight base with yy. Assume that y(e1)≤…≤y(er)y(e_1)\leq \ldots \leq y(e_r). For each element e∉Be\notin B, let CeC_e be the fundamental circuit in B+eB+e. Then we define y′y' as follows. y′(e)={y(e)e∈Bmine∈Cey(e)e∉B y'(e)= \begin{cases} y(e) & e\in B\\ \min\limits_{e\in C_e} y(e) &e\notin B \end{cases}

One can easily verify that y′(e)≤y(e)y'(e)\leq y(e) for all ee and BB is still the minimum weight base under weights y′y'. Now it remains to show that y′∈P′y'\in P'.
  1. Every element is in a minimum base. For e∈Be\in B this is automatically satisfied. We consider e∉Be\notin B. Let f∈Cef\in C_e be the element in the fundamental circuit of B+eB+e with smallest weight y(e)y(e). Be=B+e−fB^e=B+e-f is a base and we have y′(Be)=y′(B)y'(B^e)=y'(B).
  2. For all base B′B', y′(B′)≥1y'(B')\geq 1 holds since y′(B′)≥y′(B)=y(B)≥1y'(B')\geq y'(B) = y(B)\geq 1.

Proposition 4 shows that we can easily convert any solution to base hitting set (y∈Py\in P) to a more well-behaved solution (y′∈P′y'\in P'). Note that our final goal is to find some special optimal solution y′∈{0,c}Ey'\in \{0,c\}^E. Thus we want to analyse the optimal y′y' further.

We are solving max⁡y′{∑ew(e)y′(e)|y′∈P′}\max_{y'} \left\{ \sum_e w(e)y'(e)| y'\in P' \right\}. Notice that the minimum weight base under weight y′y' should always have weight 1. We want to prove that for any weight ww there is an optimal y′y' with only one non-zero value. Thus we consider expressing the solution with values in y′y'. Suppose we have computed the optimal y′y' and let θ1<…<θh\theta_1 < \ldots < \theta_h be the set of distinct values in y′y'. Let μi\mu_i be the number of edges with y′(e)=θiy'(e)=\theta_i. One immediate observation is that the objective ∑ew(e)y′(e)\sum_e w(e)y'(e) can be written as ∑iθiμi\sum_i \theta_i \mu_i. Let vi=r({e:y′(e)≤θi})−r({e:y′(e)≤θi−1})v_i=r(\left\{ e: y'(e)\leq \theta_{i} \right\})-r(\left\{ e: y'(e)\leq \theta_{i-1} \right\}) be the rank increment when involving elements with y′(e)=θiy'(e)=\theta_i. Another immediate observation is that the weight of minimum base is ∑e∈By′(e)=∑iviθi=1\sum_{e\in B} y'(e)=\sum_i v_i\theta_i=1. Based on these observations we write the following LP for θ\theta.

min∑iμiθis.t.∑iviθi=10≤θ1≤θ2≤…≤θh \begin{aligned} \min& & &\sum_i \mu_i\theta_i \\ s.t.& & &\sum_i v_i\theta_i = 1\\ & & &0 \leq \theta_1\leq \theta_2\leq \ldots \leq \theta_h \end{aligned}

Suppose the optimal y′y' is given, we can compute the optimal θ\theta in the above LP and recover another solution y″y'' to base hitting set. One can see that y″y'' is still in P′P'. This LP has h+1h+1 linearly independent constraints and hh variables. Thus only hh of the constraints are tight. We have already known that ∑iviθi=1\sum_i v_i\theta_i = 1 must be tight. Then there is always an optimal solution θ\theta such that 0=θ1=…=θk<θk+1=…=θh=c0=\theta_1=\ldots=\theta_k < \theta_{k+1}=\ldots = \theta_h =c. Let FF be the set of elements with y″(e)=0y''(e)=0. Note that the minimum weight base contains r(F)r(F) elements of FF. Thus we known that c=1r(E)−r(F)c=\frac{1}{r(E)-r(F)}. The objective is ∑e∈Ew(e)y″(e)=∑e∈E−Fw(e)y″(e)=∑e∈E−Fw(e)r(E)−r(F)\sum_{e\in E} w(e)y''(e)=\sum_{e\in E-F}w(e)y''(e)=\frac{\sum_{e\in E-F} w(e)}{r(E)-r(F)}.
Theorem5

Minimum fractional base covering is α(M)\alpha(M).

The proof is similar to and easier than the previous one. The corresponding polyhedron in LP3LP3 becomes {x|xTχF≤r(F)∀F⊂E}\{x| x^T\chi^{F}\leq r(F)\; \forall F\subset E\} which is exactly the independence polytope. Similarly, constructive proof for base covering exists [5].

Note that these two theorems can be generalized to weighted packing and covering of matroid bases.

2.2 Integral gap

It is known that the integral base packing number is ⌊σ(M)⌋\left\lfloor \sigma(M) \right\rfloor and the integral base covering number is ⌈α(M)⌉\left\lceil \alpha(M) \right\rceil. Thus the integral gap for both base packing and covering are quite small.

In [3] there are stronger theorems describing the relations between integral packing/covering number and σ\sigma or α\alpha.
Theorem6

Let ε∈[0,1)\varepsilon\in [0,1) be the fractional part of σ(M)\sigma(M) or α(M)\alpha(M), then there exists a packing(covering) of size ⌊σ(M)⌋\left\lfloor \sigma(M) \right\rfloor(⌈α(M)⌉\left\lceil \alpha(M) \right\rceil), one of the independnet sets in the packing(covering) is of size at most ε⋅r(M)\varepsilon\cdot r(M).

2.3 Duality

Applying the rank function of matroid dual derives the following (Theorem 1 in [2]),
Theorem7

For matroid MM without any loop or coloop, σ(M*)=α(M)α(M)−1\sigma(M^*)=\frac{\alpha(M)}{\alpha(M)-1}

Another relation worth noting is hitting set and set covering. The hitting set problem for matroid bases is known as computing the cogirth of the matroid. However, base covering is not a dual problem for cogirth. Sets in the corresponding hitting set problem of set covering is Se={B|e∈B}S_e=\left\{ B|e\in B \right\} for all e∈Ee\in E.

3 Computing the strength and density

For graphic matroids, the strength and fractional arboricity are known to be computable in strongly polynomial time. See chapter 51.4 in [1] and this notes.

The idea is to consider the dual problem which has only |E||E| variables. If there is a separation oracle for testing whether a dual solution xx is feasible, then ellipsoid method can be used for a polynomial time algorithm.

For spanning tree packing the dual is graph min-cut problem, which is easy for graphic matroids but NP-Hard for general matroids (to find the cogirth). The separation oracle = find minimum weight base. Chekuri and Quanrud [6] discovered near-linear time approximation scheme for some implicit fraction packing problems. For fractional base packing, their algorithm outputs a (1-ε)-approximation with Õ(n/ϵ2)\tilde O(n/\epsilon^2) independence oracle calls. For the capacitated version, the number of oracle calls becomes Õ(rn/ϵ2)\tilde O(rn/\epsilon^2). Almost at the same time, Jérôme Galtier published similar results for graphs [7] and for matroids [5].

For spanning tree covering the dual is finding a maximum edge set whose intersection with each spanning tree is at most 1. This problem can be thought as a set cover, in which the sets are {T|e∈T}\left\{ T|e\in T \right\} for each edge ee. The separation oracle solves the following problem: given edge weight x:E→[0,1]x:E\to [0,1], is there a spanning tree with weight greater than 1? We can simply find a matroid base with the largest weight. Thus for general matroid we can find the fractional arboricity through ellipsoid method.

References

[1]
A. Schrijver, Combinatorial optimization Polyhedra and Efficiency, Springer, 2004.
[2]
P.A. Catlin, J.W. Grossman, A.M. Hobbs, H.-J. Lai, Fractional arboricity, strength, and principal partitions in graphs and matroids, Discrete Applied Mathematics. 40 (1992) 285–302 10.1016/0166-218X(92)90002-R.
[3]
G. Fan, H. Jiang, P. Li, D.B. West, D. Yang, X. Zhu, Extensions of matroid covering and packing, European Journal of Combinatorics. 76 (2019) 117–122 10.1016/j.ejc.2018.09.010.
[4]
A. Schrijver, Polyhedral proof methods in combinatorial optimization, Discrete Applied Mathematics. 14 (1986) 111–133 10.1016/0166-218X(86)90056-9.
[5]
J. Galtier, Fast approximation of matroid packing and covering, Annals of Operations Research. 271 (2018) 575–598 10.1007/s10479-018-2756-8.
[6]
C. Chekuri, K. Quanrud, Near-Linear Time Approximation Schemes for some Implicit Fractional Packing Problems, in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2017: pp. 801–820 10.1137/1.9781611974782.51.
[7]
J. Galtier, Computing weighted strength and applications to partitioning, SIAM Journal on Discrete Mathematics. 32 (2018) 2747–2782 10.1137/15M102914X.