Matroid intersection
Encyclopedia
In combinatorial optimization
, the matroid intersection problem is to find a largest common independent set in two matroid
s over the same ground set. If the elements of the matroid are assigned real weights, the weighted matroid intersection problem is to find a common independent set with the maximum possible weight. These problems generalize many problems in combinatorial optimization including finding maximum matchings and maximum weight matchings in bipartite graph
s and finding arborescence
s in directed graph
s.
. One may define a matroid MU on the ground set E, in which a set of edges is independent if no two of the edges have the same endpoint in U. Similarly one may define a matroid MV in which a set of edges is independent if no two of the edges have the same endpoint in V. Any set of edges that is independent in both MU and MV has the property that no two of its edges share an endpoint; that is, it is a matching. Thus, the largest common independent set of MU and MV is a maximum matching in G.
when three matroids are involved, instead of only two.
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
, the matroid intersection problem is to find a largest common independent set in two matroid
Matroid
In combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....
s over the same ground set. If the elements of the matroid are assigned real weights, the weighted matroid intersection problem is to find a common independent set with the maximum possible weight. These problems generalize many problems in combinatorial optimization including finding maximum matchings and maximum weight matchings in bipartite graph
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
s and finding arborescence
Arborescence
Arborescence can refer to multiple topics:* A word; see Wiktionary:arborescence* Arborescence : a type of directed graph* Arborescence : an album by Ozric Tentacles...
s in directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
s.
Example
Let G = (U,V,E) be a bipartite graphBipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
. One may define a matroid MU on the ground set E, in which a set of edges is independent if no two of the edges have the same endpoint in U. Similarly one may define a matroid MV in which a set of edges is independent if no two of the edges have the same endpoint in V. Any set of edges that is independent in both MU and MV has the property that no two of its edges share an endpoint; that is, it is a matching. Thus, the largest common independent set of MU and MV is a maximum matching in G.
Extension
The matroid intersection problem becomes NP-hardNP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
when three matroids are involved, instead of only two.