en>Timflutre: improve description of his 1989 Nature paper and add ref

2013-09-03T06:00:50Z

improve description of his 1989 Nature paper and add ref

New page

The '''matroid partitioning''' problem is a problem arising in the mathematical study of [[matroid]]s and in the design and analysis of [[algorithm]]s, in which the 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 [[tree (graph theory)|forests]] needed to cover all of its edges. Matroid partitioning may be solved in [[polynomial time]], given an [[matroid oracle|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 [[Matroid rank|ranks]] and independent sets in matroid sums, and to compute the largest common independent set in the [[matroid intersection|intersection]] of two given matroids.<ref name="fgt">{{citation
| last1 = Scheinerman | first1 = Edward R. | author1-link = Ed Scheinerman
| last2 = Ullman | first2 = Daniel H.
| contribution = 5. Fractional arboricity and matroid methods
| isbn = 0-471-17864-0
| location = New York
| mr = 1481157
| pages = 99–126
| publisher = John Wiley & Sons Inc.
| series = Wiley-Interscience Series in Discrete Mathematics and Optimization
| title = Fractional graph theory
| year = 1997}}.</ref>

==Example==
[[File:K44 arboricity.svg|thumb|A partition of the edges of the [[complete bipartite graph]] ''K''<sub>4,4</sub> into three forests, showing that it has arboricity at most three]]
The [[arboricity]] of an [[undirected graph]] is the minimum number of [[tree (graph theory)|forests]] into which its edges can be partitioned, or equivalently (by adding overlapping edges to each forest as necessary) the minimum number of [[spanning tree|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 <math>H</math> of the given graph <math>G</math>, of the quantity <math>\left\lceil\frac{|E(H)|}{|V(H)|-1}\right\rceil</math>.<ref>{{citation
| last = Nash-Williams | first = C. St. J. A. | author-link = Crispin St. J. A. Nash-Williams
| doi = 10.1112/jlms/s1-39.1.12
| issue = 1
| journal = [[Journal of the London Mathematical Society]]
| mr = 0161333
| page = 12
| title = Decomposition of finite graphs into forests
| volume = 39
| year = 1964}}.</ref>

The forests of a graph form the independent sets of the associated [[graphic matroid]], and the quantity <math>|V(H)|-1</math> appearing in Nash-Williams' formula is the rank of the graphic matroid of <math>H</math>, 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 <math>|E(H)|</math> elements of this matroid cannot be partitioned into fewer than <math>\frac{|E(H)|}{|V(H)|-1}</math> independent subsets is then just an application of the [[pigeonhole principle]] saying that, if <math>x</math> items are partitioned into sets of size at most <math>y</math>, then at least <math>x/y</math> 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.<ref name="fgt"/>

==Formula for partition size==
To generalize Nash-Williams' formula, one may replace <math>G</math> by a matroid <math>M</math>, and the subgraph <math>H</math> of <math>G</math> with a [[matroid minor|restriction]] <math>M|S</math> of <math>M</math> to a subset <math>S</math> of its elements. The number of edges of the subgraph <math>H</math> becomes, in this generalization, the cardinality <math>|S|</math> of the selected subset, and the formula <math>|V(H)|-1</math> for the maximum size of a forest in <math>H</math> becomes the rank <math>r(S)</math>. Thus, the minimum number of independent sets in a partition of the given matroid <math>M</math> should be given by the formula
:<math>k(M)=\max_S \left\lceil\frac{|S|}{r(S)}\right\rceil,</math>
which is valid for all matroids and was given an algorithmic proof by {{harvtxt|Edmonds|1965}}.<ref name="fgt"/><ref name="e65">{{citation
| last = Edmonds | first = Jack | author-link = Jack Edmonds
| journal = Journal of Research of the National Bureau of Standards
| mr = 0190025
| pages = 67–72
| title = Minimum partition of a matroid into independent subsets
| url = http://cdm16009.contentdm.oclc.org/cdm/ref/collection/p13011coll6/id/66398
| volume = 69B
| year = 1965}}.</ref>

==Algorithms==
The first algorithm for matroid partitioning was given by {{harvtxt|Edmonds|1965}}.<ref name="e65"/> 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 <math>x</math> 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 <math>x</math>, and a special element <math>\bot_i</math> for each of the <math>k</math> independent sets in the current partition. It then forms a directed graph <math>G_x</math> on this node set, with a directed arc <math>\bot_i\rightarrow y</math> for each matroid element <math>y</math> that can be added to partition set <math>i</math> without causing it to become dependent, and with a directed arc <math>z\rightarrow y</math> for each pair of matroid elements <math>(y,z)</math> such that removing <math>z</math> from its partition and replacing it with <math>y</math> forms another independent set.<ref name="fgt"/><ref name="e65"/>

If this graph contains a [[directed path]] from an element <math>\bot_i</math> to the newly considered element <math>x</math>, then the shortest such path (or more generally any path that does not have any shortcutting edges) describes a sequence of changes that can be made simultaneously to the partition sets in order to form a new partition, with the same number of sets, that also includes <math>x</math>. In this case, the algorithm performs these changes and continues. If, on the other hand, no such path exists, then let <math>S</math> consist of the matroid elements from which <math>x</math> is [[reachability|reachable]] in <math>D</math>. Each set in the current partition must be a maximal independent set in <math>M|S</math>, for if some element <math>y</math> of <math>S</math> could be added to partition set <math>i</math> in the restriction, then either there would exist an arc <math>\bot_i\rightarrow y</math> (if partition set <math>i</math> is non-maximal in the full matroid <math>M</math>) or an arc <math>z\rightarrow y</math> where <math>z\notin S</math> (if the partition set is non-maximal in <math>S</math> but maximal in the full matroid). In either case the existence of this arc contradicts the assumed construction of the set <math>S</math>, and the contradiction proves that each partition set is maximal. Thus, by the easy direction of the matroid partitioning formula, the number of sets needed to partition <math>S</math> is at least
:<math>\left\lceil\frac{|S|}{r(S)}\right\rceil=\left\lceil\frac{kr(S)+1}{r(S)}\right\rceil=k+1</math>,
so in this case the algorithm may find an optimal partition by placing <math>x</math> into its own new independent set and leaving the other independent sets unchanged.<ref name="fgt"/><ref name="e65"/>

The overall algorithm, then, considers each element <math>x</math> of the given matroid in turn, constructs the graph <math>G_x</math>, tests which nodes can reach <math>x</math>, and uses this information to update the current partition so that it includes <math>x</math>. 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.<ref name="fgt"/><ref name="e65"/>

Although this algorithm depends only on the existence of an [[matroid oracle|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 matroid]]s) from which a particular partitioning problem has been defined.<ref name="gw92">{{citation
| last1 = Gabow | first1 = Harold N.
| last2 = Westermann | first2 = Herbert H.
| doi = 10.1007/BF01758774
| issue = 5-6
| journal = Algorithmica
| mr = 1154585
| pages = 465–497
| title = Forests, frames, and games: algorithms for matroid sums and applications
| volume = 7
| year = 1992}}.</ref>

==Related problems==
A [[matroid sum]] <math>\sum_i M_i</math> (where each <math>M_i</math> 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, and its correctness can be used to prove that a matroid sum is necessarily a matroid.<ref name="e65"/><ref name="gw92"/>

The [[matroid intersection]] problem of finding the largest set that is independent in two matroids <math>M_1</math> and <math>M_2</math> may be solved by turning it into an equivalent matroid sum problem: if <math>B</math> is a basis of the sum <math>M_1+M_2^*</math>, where <math>M_2^*</math> is the dual of <math>M_2</math>, then <math>B</math> must have full rank in <math>M_2^*</math> and removing a maximal independent set of <math>M_2^*</math> from <math>B</math> leaves a maximum intersection.<ref>{{citation
| last = Edmonds | first = Jack
| contribution = Submodular functions, matroids, and certain polyhedra
| location = New York
| mr = 0270945
| pages = 69–87
| publisher = Gordon and Breach
| title = Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969)
| year = 1970}}.</ref>

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.<ref name="gw92"/> 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.<ref name="fgt"/>

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 (graph theory)|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).<ref name="fgt"/>

==References==
{{reflist}}

[[Category:Matroid theory]]

Jacques Laskar - Revision history

en>Timflutre: improve description of his 1989 Nature paper and add ref