Subdivision into few independent sets
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 formula_1 of the given graph formula_2, of the quantity formula_3,
so in this case the algorithm may find an optimal partition by placing formula_4 into its own new independent set and leaving the other independent sets unchanged.
The overall algorithm, then, considers each element formula_4 of the given matroid in turn, constructs the graph formula_6, tests which nodes can reach formula_4, and uses this information to update the current partition so that it includes formula_4. 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.
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. 
Related problems.
A matroid sum formula_9 (where each formula_10 is a matroid) is itself a matroid, having as its elements the union of the elements of the summands. A set is independent in the sum if it can be partitioned into sets that are independent within each summand. The matroid partitioning algorithm generalizes to the problem of testing whether a set is independent in a matroid sum. Its correctness can be used to prove that a matroid sum is necessarily a matroid. 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 presents an algorithm for solving this problem on "O"("n") "n"-element matroids using formula_11 calls to an independence oracle.
The matroid intersection problem is finding the largest set that is independent in two matroids formula_12 and formula_13. It may be solved by turning it into an equivalent matroid sum problem: if formula_14 is a basis of the sum formula_15, where formula_16 is the dual of formula_13, then formula_14 must have full rank in formula_16 and removing a maximal independent set of formula_16 from formula_14 leaves a maximum intersection.
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. The fractional set packing and set covering problems associated with a matroid (that is, assign a weight to each independent set in such a way that for every element the total weight of the sets containing it is at most one or at least one, maximizing or minimizing the total weight of all the sets, respectively) can also be solved in polynomial time using matroid partitioning methods.
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).
Matroid-constrained number partitioning is a different problem in which "k" (the number of subsets in the partition) is fixed. There are "k" different matroids over the same ground set, and the goal is to partition the ground set into "k" subsets, such that each subset "i" is an independent set in matroid "i". Subject to this constraint, some objective function should be minimized. In a generalization of this variant, each of the "k" matroids has a weight, and the objective function depends on the weights (maximum weight, minimum weight or sum of weights).
References.
 ;templatestyles src="Reflist/styles.css" / ;