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.

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 ${\displaystyle H}$ of the given graph ${\displaystyle G}$, of the quantity ${\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 ${\displaystyle |V(H)|-1}$ appearing in Nash-Williams' formula is the rank of the graphic matroid of ${\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 ${\displaystyle |E(H)|}$ elements of this matroid cannot be partitioned into fewer than ${\displaystyle {\frac {|E(H)|}{|V(H)|-1}}}$ independent subsets is then just an application of the pigeonhole principle saying that, if ${\displaystyle x}$ items are partitioned into sets of size at most ${\displaystyle y}$, then at least ${\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.

To generalize Nash-Williams' formula, one may replace ${\displaystyle G}$ by a matroid ${\displaystyle M}$, and the subgraph ${\displaystyle H}$ of ${\displaystyle G}$ with a restriction ${\displaystyle M|S}$ of ${\displaystyle M}$ to a subset ${\displaystyle S}$ of its elements. The number of edges of the subgraph ${\displaystyle H}$ becomes, in this generalization, the cardinality ${\displaystyle |S|}$ of the selected subset, and the formula ${\displaystyle |V(H)|-1}$ for the maximum size of a forest in ${\displaystyle H}$ becomes the rank ${\displaystyle r(S)}$. Thus, the minimum number of independent sets in a partition of the given matroid ${\displaystyle M}$ should be given by the formula

This formula is indeed valid, and it was given an algorithmic proof by Edmonds (1965). In other words, a matroid can be partitioned into at most ${\displaystyle k}$ independent subsets, if-and-only-if for every subset ${\displaystyle S}$ of ${\displaystyle M}$, the cardinality of ${\displaystyle S}$ is at most ${\displaystyle k\cdot r(S)}$.

The first algorithm for matroid partitioning was given by Edmonds (1965). 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. At each step, when considering an element ${\displaystyle x}$ 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 ${\displaystyle x}$, and a special element ${\displaystyle \bot _{i}}$ for each of the ${\displaystyle k}$ independent sets in the current partition. It then forms a directed graph ${\displaystyle G_{x}}$ on this node set, with a directed arc ${\displaystyle \bot _{i}\rightarrow y}$ for each matroid element ${\displaystyle y}$ that can be added to partition set ${\displaystyle i}$ without causing it to become dependent, and with a directed arc ${\displaystyle z\rightarrow y}$ for each pair of matroid elements ${\displaystyle (y,z)}$ such that removing ${\displaystyle z}$ from its partition and replacing it with ${\displaystyle y}$ forms another independent set.

Now there are two cases:

so in this case the algorithm may find an optimal partition by placing ${\displaystyle x}$ into its own new independent set and leaving the other independent sets unchanged.