Matroid partitioning is a problem arising in the mathematical study of matroids and in the design and analysis of algorithms. Its goal is to partition the elements of a matroid into as few independent sets as possible. An example is the problem of computing the arboricity of an undirected graph, the minimum number of forests needed to cover all of its edges. Matroid partitioning may be solved in polynomial time, given an independence oracle for the matroid. It may be generalized to show that a matroid sum is itself a matroid, to provide an algorithm for computing ranks and independent sets in matroid sums, and to compute the largest common independent set in the intersection of two given matroids.
Example
The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned, or equivalently (by adding overlapping edges to each forest as necessary) the minimum number of spanning forests whose union is the whole graph. A formula proved by Crispin Nash-Williams characterizes the arboricity exactly: it is the maximum, over all subgraphs H {\displaystyle H} of the given graph G {\displaystyle G} , of the quantity ⌈ | E ( H ) | | V ( H ) | − 1 ⌉ {\displaystyle \left\lceil {\frac {|E(H)|}{|V(H)|-1}}\right\rceil } . The forests of a graph form the independent sets of the associated graphic matroid, and the quantity | V ( H ) | − 1 {\displaystyle |V(H)|-1} appearing in Nash-Williams' formula is the rank of the graphic matroid of H {\displaystyle H} , the maximum size of one of its independent sets. Thus, the problem of determining the arboricity of a graph is exactly the matroid partitioning problem for the graphic matroid. The fact that the | E ( H ) | {\displaystyle |E(H)|} elements of this matroid cannot be partitioned into fewer than | E ( H ) | | V ( H ) | − 1 {\displaystyle {\frac {|E(H)|}{|V(H)|-1}}} independent subsets is then just an application of the pigeonhole principle saying that, if x {\displaystyle x} items are partitioned into sets of size at most y {\displaystyle y} , then at least x / y {\displaystyle x/y} sets are needed. The harder direction of Nash-Williams' formula, which can be generalized to all matroids, is the proof that a partition of this size always exists.
Formula for partition size To generalize Nash-Williams' formula, one may replace G {\displaystyle G} by a matroid M {\displaystyle M} , and the subgraph H {\displaystyle H} of G {\displaystyle G} with a restriction M | S {\displaystyle M|S} of M {\displaystyle M} to a subset S {\displaystyle S} of its elements. The number of edges of the subgraph H {\displaystyle H} becomes, in this generalization, the cardinality | S | {\displaystyle |S|} of the selected subset, and the formula | V ( H ) | − 1 {\displaystyle |V(H)|-1} for the maximum size of a forest in H {\displaystyle H} becomes the rank r ( S ) {\displaystyle r(S)} . Thus, the minimum number of independent sets in a partition of the given matroid M {\displaystyle M} should be given by the formula
… excerpt ends here. Continue reading the full article.
