Tags: matroid, optimization, combinatorics

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,\mathop{\mathrm{\mathcal I}})$ and its bases $\mathop{\mathrm{\mathcal B}}$, find

(minimum base covering) the min number of bases whose union is $E$, and
(maximum base packing) the max number of pairwise disjoint bases.

These problems can be formulated with the following integer programs, base packing: \[\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 \set{0,1} & &\forall \text{ base $B$} \end{align*}\]

base covering: \[\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 \set{0,1} & &\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,\mathop{\mathrm{\mathcal I}})$ be the matroid. The minimum number of bases that cover the groundset is $\arg\min\limits_k r_{k}(E)=|E|$, where $r_{k}(\cdot)$ is the rank function of $M^k$.
matroid base packing ≈ matroid union. Maximum integral base packing number is $\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 $\alpha(G)$ equals to $\max\limits_{\emptyset \subsetneq X\subset E}\frac{|X|}{r(X)}$. Define the density for a matroid $M$ as $\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)$ equals to $\max \frac{|E[\mathcal P]|}{|\mathcal P|-1}$, where the maximum is taken among all partitions $\mathcal P$ of $V$.

The fraction in above theorem can be rewrite as $\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, $\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,

\[ \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 $\sigma(M)$.

Proof

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

\[\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 \R^\Pi_+ \end{align*}\]

and the dual of $LP2$, \[\begin{align*} LP3=\min& & lx& & &\\ s.t.& & x^T\chi^{E\setminus F} &\geq r(E)-r(F) & &\forall F\subsetneq E\\ & & x&\in \R^E_+ & & \end{align*}\]

We first prove that the polyhedron in $LP3$, $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 $M$. One can see that $B(M)\subseteq Q$. Now suppose $Q$ is larger than $B(M)$, there must exists $x\in Q$ such that $x(U)>r(U)$ for some $U\subseteq E$. Thus $\mathop{\mathrm{OPT}}(LP3)>\mathop{\mathrm{OPT}}(LP1)$. However, for the optimal solution $x$ to $LP1$ and any feasible solution $y$ to $LP2$ we have \[ \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)$.

Recall that $\sigma(M)=\min_{F\subsetneq E}\frac{|E\setminus F|}{r(E)-r(F)}$. Note that $\sigma(M)\geq 1$. $\sigma(M)$ can be interpreted as the largest $\lambda>1$ such that $|E\setminus F| \geq \lambda(r(E)-r(F))$ holds for all $F\subsetneq E$. Hence $\sigma(M)=\max \{\lambda | \mathbf 1\in \lambda B(M)\}$ since $Q=B(M)$. For fixed $\lambda$, $\mathbf 1 \in \lambda B(M)$ if and only if there exists $\lambda_b\geq 0$ for all bases of $M$ such that $\sum_b \lambda_b=\lambda$ and $\sum_b \lambda_b \chi^b\leq 1$. Hence this shows $\sigma(M)$ is exactly the base packing LP $\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\subset E$ in $\sigma(M)$ from any optimal solution of hitting set LP(dual to base packing).

The idea is to show that any fraction solution $y$ to base hitting set can be converted to another solution $y'$ such that $y'(e)\in \set{0,c}$ for some global constant $c$ and $\sum_e w(e)y'(e)\leq \sum_e w(e)y(e)$.

Define two sets $P, P'\in \R^{|E|}$, \[\begin{equation*} \begin{aligned} P &=\set{y\in \R^{|E|}: y(e)\geq 0 \;\forall e\in E; y(B)\geq 1 \; \forall \text{ base B}},\\ P' &=\set{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)}. \end{aligned} \end{equation*}\]

$P'$ is contained in $P$ and every element is in a minimum base with respect to weights $y:E\to \R$.

Proposition4

Let $y\in P$. There exists $y'\in P'$ s.t. $y(e)\geq y'(e)$ for all $e$.

Proof

The proof is contrustive. Let $B=\set{e_1,\ldots, e_r}$ be a minimum weight base with $y$. Assume that $y(e_1)\leq \ldots \leq y(e_r)$. For each element $e\notin B$, let $C_e$ be the fundamental circuit in $B+e$. Then we define $y'$ as follows. \[\begin{equation*} y'(e)= \begin{cases} y(e) & e\in B\\ \min\limits_{e\in C_e} y(e) &e\notin B \end{cases} \end{equation*}\]

One can easily verify that $y'(e)\leq y(e)$ for all $e$ and $B$ is still the minimum weight base under weights $y'$. Now it remains to show that $y'\in P'$.

Every element is in a minimum base. For $e\in B$ this is automatically satisfied. We consider $e\notin B$. Let $f\in C_e$ be the element in the fundamental circuit of $B+e$ with smallest weight $y(e)$. $B^e=B+e-f$ is a base and we have $y'(B^e)=y'(B)$.
For all base $B'$, $y'(B')\geq 1$ holds since $y'(B')\geq y'(B) = y(B)\geq 1$.

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

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

\[\begin{equation*} \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} \end{equation*}\]

Suppose the optimal $y'$ is given, we can compute the optimal $\theta$ in the above LP and recover another solution $y''$ to base hitting set. One can see that $y''$ is still in $P'$. This LP has $h+1$ linearly independent constraints and $h$ variables. Thus only $h$ of the constraints are tight. We have already known that $\sum_i v_i\theta_i = 1$ must be tight. Then there is always an optimal solution $\theta$ such that $0=\theta_1=\ldots=\theta_k < \theta_{k+1}=\ldots = \theta_h =c$. Let $F$ be the set of elements with $y''(e)=0$. Note that the minimum weight base contains $r(F)$ elements of $F$. Thus we known that $c=\frac{1}{r(E)-r(F)}$. The objective is $\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 $\alpha(M)$.

The proof is similar to and easier than the previous one. The corresponding polyhedron in $LP3$ becomes $\{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 $\floor{\sigma(M)}$ and the integral base covering number is $\ceil{\alpha(M)}$. 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 $\varepsilon\in [0,1)$ be the fractional part of $\sigma(M)$ or $\alpha(M)$, then there exists a packing(covering) of size $\floor{\sigma(M)}$($\ceil{\alpha(M)}$), one of the independnet sets in the packing(covering) is of size at most $\varepsilon\cdot r(M)$.

2.3 Duality

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

Theorem7

For matroid $M$ without any loop or coloop, \[\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 $S_e=\set{B|e\in B}$ for all $e\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|$ variables. If there is a separation oracle for testing whether a dual solution $x$ 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 $\tilde O(n/\epsilon^2)$ independence oracle calls. For the capacitated version, the number of oracle calls becomes $\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 $\set{T|e\in T}$ for each edge $e$. The separation oracle solves the following problem: given edge weight $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.

Matroid base packing and covering