Matroid partitioning
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.
[1] 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
[2] The forests of a graph form the independent sets of the associated graphic matroid, and the quantity
appearing in Nash-Williams' formula is the rank of the graphic matroid of
, the maximum size of one of its independent sets.
independent subsets is then just an application of the pigeonhole principle saying that, if
items are partitioned into sets of size at most
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.
Thus, the minimum number of independent sets in a partition of the given matroid
[3] It is an incremental augmenting-path algorithm that considers the elements of the matroid one by one, in an arbitrary order, maintaining at each step of the algorithm an optimal partition for the elements that have been considered so far.
that has not yet been placed into a partition, the algorithm constructs a directed graph that has as its nodes the elements that have already been partitioned, the new element
independent sets in the current partition.
on this node set, with a directed arc
, and uses this information to update the current partition so that it includes
At each step, the partition of the elements considered so far is optimal, so when the algorithm terminates it will have found an optimal partition for the whole matroid.
Proving that this algorithm is correct requires showing that a shorcut-free path in the auxiliary graph always describes a sequence of operations that, when performed simultaneously, correctly preserves the independence of the sets in the partition; a proof of this fact was given by Edmonds.
Because the algorithm only increases the number of sets in the partition when the matroid partitioning formula shows that a larger number is needed, the correctness of this algorithm also shows the correctness of the formula.
[1][3] Although this algorithm depends only on the existence of an independence oracle for its correctness, faster algorithms can be found in many cases by taking advantage of the more specialized structure of specific types of matroids (such as graphic matroids) from which a particular partitioning problem has been defined.
The matroid partitioning algorithm generalizes to the problem of testing whether a set is independent in a matroid sum.
[3][4] An extended problem, that is also sometimes called matroid partition, is to find a largest set that is independent in the matroid sum, that is, a largest set that can be partitioned into sets that are disjoint in each input matroid.
Cunningham[5] presents an algorithm for solving this problem on O(n) n-element matroids using
It may be solved by turning it into an equivalent matroid sum problem: if
and removing a maximal independent set of
[6] Matroid partitioning is a form of set cover problem, and the corresponding set packing problem (find a maximum number of disjoint spanning sets within a given matroid) is also of interest.
It can be solved by algorithms similar to those for matroid partitioning.
[1] As well as its use in calculating the arboricity of a graph, matroid partitioning can be used with other matroids to find a subgraph of a given graph whose average degree is maximum, and to find the edge toughness of a graph (a variant of graph toughness involving the deletion of edges in place of vertices).
Subject to this constraint, some objective function should be minimized.
