Tags: matroid, optimization, combinatorics

Recently(actually, not that recent), I have been interested in the fractional version of matroid base packing and covering problems.

As far as I know, there are few text books in combinatorial optimization cover topics in matroid base packing, while matroid base covering(matroid partition problem) is everywhere. Packing and covering of trees in graphs is discussed in chapter 51 of [1].

1 Base packing & base covering

Problem1

Given a matroid $M = (E, I)$ and its bases $B$ , find

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

These problems can be formulated with the following integer programs, base packing: $max s . t . B : e \in B \sum x_{B} x_{B} B \in B \sum x_{B} \leq 1 \forall e \in E \in {0, 1}$

base covering: $min s . t . B : e \in B \sum x_{B} x_{B} B \in B \sum x_{B} \geq 1 \forall e \in E \in {0, 1}$

In general integer programs are hard. Here the base packing and covering problems have exponential number of variables. If nothing is known for these two problems, people natually study their linear relaxation.

Just a note. It is widely known that any linear program with a rank- $m$ constraint matrix has a support with size no larger than $m$ . For similar problem on integer programming, one might think that there is also a small support based on the knowledge that the optimal solution for the integer program is simply a integer point inside the feasible region. However, the size of support for integer programs is not that small. Currently the best known upperbound is roughly $m \cdot polylog (∥ A ∥_{1})$ , see this paper.

Actually these two problems are not hard on general matroids. They can both be solved in polynomial number of independence oracle calls.

matroid base covering = matroid partitioning ≈ matroid union. Let $M = (E, I)$ be the matroid. The minimum number of bases that cover the groundset is $ar g k min 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 $ar g k max r_{k} (E) = k r (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.

Another note. The base covering number may be much larger than the base packing number, since $E - B_{k}$ may not be independent for $M$ . ( $B_{k}$ is the union of bases in the optimal packing)

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)$ equals to $\emptyset ⊊ X \subset E max \frac{∣ X ∣}{r ( X )}$ . Define the density for a matroid $M$ as $α (M) = \emptyset ⊊ X \subset E max \frac{∣ X ∣}{r ( X )}$ . The name “density” comes from [2]. I use symbol $α$ 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 [ P ] ∣}{∣ P ∣ - 1}$ , where the maximum is taken among all partitions $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, $σ (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 \frac{∣ X ∣}{r ( X )} \geq \frac{∣ E ∣}{r ( E )} \geq min \frac{∣ E - F ∣}{r ( E ) - r ( F )} = σ (M) .$

Theorem3

Maximum fractional base packing number is $σ (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 $Π$ be the powerset of $E$ . Consider the following linear programs, $L P 1 = min s . t . l x x \in B (M)$

$L P 2 = max F ⊊ E \sum y_{E ∖ F} s . t . F ⊊ E \sum y_{E ∖ F} χ^{E ∖ F} y (r (E) - r (F)) \leq l \in R_{+}^{Π}$

and the dual of $L P 2$ , $L P 3 = min s . t . x^{T} χ^{E ∖ F} x l x \geq r (E) - r (F) \forall F ⊊ E \in R_{+}^{E}$

We first prove that the polyhedron in $L P 3$ , $Q = {x ∣ x \geq 0, x^{T} χ^{E ∖ F} \geq r (E) - r (F) \forall F ⊊ 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 $OPT (L P 3) > OPT (L P 1)$ . However, for the optimal solution $x$ to $L P 1$ and any feasible solution $y$ to $L P 2$ we have $OPT (L P 1) \geq F ⊊ E \sum y_{E ∖ F} χ^{E ∖ F} \cdot x = F ⊊ E \sum y_{E ∖ F} (e \in E \sum x_{e} - e \in F \sum x_{e}) \geq F ⊊ E \sum y_{E ∖ F} (r (E) - r (F)) = OPT (L P 3)$ Hence $Q = B (M)$ .

Recall that $σ (M) = min_{F ⊊ E} \frac{∣ E ∖ F ∣}{r ( E ) - r ( F )}$ . Note that $σ (M) \geq 1$ . $σ (M)$ can be interpreted as the largest $λ > 1$ such that $∣ E ∖ F ∣ \geq λ (r (E) - r (F))$ holds for all $F ⊊ E$ . Hence $σ (M) = max {λ ∣ 1 \in λ B (M)}$ since $Q = B (M)$ . For fixed $λ$ , $1 \in λ B (M)$ if and only if there exists $λ_{b} \geq 0$ for all bases of $M$ such that $\sum_{b} λ_{b} = λ$ and $\sum_{b} λ_{b} χ^{b} \leq 1$ . Hence this shows $σ (M)$ is exactly the base packing LP $max {\sum_{b} λ_{b} ∣ \sum_{b} λ_{b} χ^{b} \leq 1, λ_{b} \geq 0 \forall b \in B}$ .

Theorem4

Minimum fractional base covering is $α (M)$ .

The proof is similar to and easier than the previous one. The corresponding polyhedron in $L P 3$ becomes ${x ∣ χ^{F} \cdot x \leq r (F) \forall F \subset E}$ which is exactly the independence polytope.

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

2.1 Integral gap

It is known that the integral base packing number is $⌊ σ (M) ⌋$ and the integral base covering number is $⌈ α (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 $σ$ or $α$ .

Theorem5

Let $ε \in [0, 1)$ be the fractional part of $σ (M)$ or $α (M)$ , then there exists a packing(covering) of size $⌊ σ (M) ⌋$ ( $⌈ α (M) ⌉$ ), one of the independnet sets in the packing(covering) is of size at most $ε \cdot r (M)$ .

2.2 Duality

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

Theorem6

For matroid $M$ without any loop or coloop, $σ (M^{*}) = \frac{α ( M )}{α ( 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} = {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.

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 \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.

On matroid base packing and covering