Matroid intersection

Last updated December 01, 2023

In combinatorial optimization, the matroid intersection problem is to find a largest common independent set in two matroids 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 graphs and finding arborescences in directed graphs.

The matroid intersection theorem, due to Jack Edmonds,^[1] says that there is always a simple upper bound certificate, consisting of a partitioning of the ground set amongst the two matroids, whose value (sum of respective ranks) equals the size of a maximum common independent set. Based on this theorem, the matroid intersection problem for two matroids can be solved in polynomial time using matroid partitioning algorithms.

Examples

Let G = (U,V,E) be a bipartite graph. One may define a partition matroid M_U 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 M_V 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 M_U and M_V 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 M_U and M_V is a maximum matching in G.

Similarly, if each edge has a weight, then the maximum-weight independent set of M_U and M_V is a Maximum weight matching in G.

Algorithms

There are several polynomial-time algorithms for weighted matroid intersection, with different run-times. The run-times are given in terms of $n$ - the number of elements in the common base-set, $r$ - the maximum between the ranks of the two matroids, $T$ - the number of operations required for a circuit-finding oracle, and $k$ - the number of elements in the intersection (in case we want to find an intersection of a specific size $k$ ).

Edmonds' algorithm uses linear programming and polyhedra.^[1]
Lawler's algorithm.^[2]
Iri and Tomizawa's algorithm^[3]
Andras Frank's algorithm^[4] uses $O(n^{3}T)$ arithmetic opreations.
Orlin and Vande-Vate's algorithm.^[5]
Cunningham's algorithm^[6] requires $O(r^{1.5}nT)$ operations on general matroids, and $O(nr^{2}\log {r})$ operations on linear matroid, for two r-by-n matrices.
Brezovec, Cornuejos and Glover^[7] present two algorithms for weighted matroid intersection.
- The first algorithm requires that all weights be integers, and finds an intersection of cardinality $k$ in time $O((n^{3}k^{2}+nkT)\cdot (1+\log {W}))$ .
- The second algorithm runs in time $O(nr\cdot (\log {n}+r+T))$ .
Huang, Kakimura and Kamiyama^[8] show that the weighted matroid intersection problem can be solved by solving W instances of the unweighted matroid intersection problem, where W is the largest given weight, assuming that all given weights are integral. This algorithm is faster than previous algorithms when W is small. They also present an approximation algorithm that finds an e-approximate solution by solving $O(\epsilon ^{-1}\log {r})$ instances of the unweighted matroid intersection problem, where r is the smaller rank of the two input matroids.
Ghosh, Gurjar and Raj^[9] study the run-time complexity of matroid intersection in the parallel computing model.
Bérczi, Király, Yamaguchi and Yokoi^[10] present strongly polynomial-time algorithms for weighted matroid intersection using more restricted oracles.

Extensions

Maximizing weight subject to cardinality

In a variant of weighted matroid intersection, called "(P_k)", the goal is to find a common independent set with the maximum possible weight among all such sets with cardinality k, if such a set exists. This variant, too, can be solved in polynomial time.^[7]

Three matroids

The matroid intersection problem becomes NP-hard when three matroids are involved, instead of only two.

One proof of this hardness result uses a reduction from the Hamiltonian path problem in directed graphs. Given a directed graph G with n vertices, and specified nodes s and t, the Hamiltonian path problem is the problem of determining whether there exists a simple path of length n − 1 that starts at s and ends at t. It may be assumed without loss of generality that s has no incoming edges and t has no outgoing edges. Then, a Hamiltonian path exists if and only if there is a set of n − 1 elements in the intersection of three matroids on the edge set of the graph: two partition matroids ensuring that the in-degree and out-degree of the selected edge set are both at most one, and the graphic matroid of the undirected graph formed by forgetting the edge orientations in G, ensuring that the selected edge set has no cycles.^[11]

Matroid parity

Another computational problem on matroids, the matroid parity problem, was formulated by Lawler^[12] as a common generalization of matroid intersection and non-bipartite graph matching. However, although it can be solved in polynomial time for linear matroids, it is NP-hard for other matroids, and requires exponential time in the matroid oracle model.^[13]

Valuated matroids

A valuated matroid is a matroid equipped with a value function v on the set of its bases, with the following exchange property: for any two distinct bases $A$ and $B$ , if $a\in A\setminus B$ , then there exists an element $b\in B\setminus A$ such that both $(A\setminus \{a\})\cup \{b\}$ and $(B\setminus \{b\})\cup \{a\}$ are bases, and : $v(A)+v(B)\leq v(B\setminus \{b\}\cup \{a\})+v(A\setminus \{a\}\cup \{b\})$ .

Given a weighted bipartite graph G = (X+Y, E) and two valuated matroids, one on X with bases set B_X and valuation v_X, and one on Y with bases B_Y and valuation v_Y, the valuated independent assignment problem is the problem of finding a matching M in G, such that M_X (the subset of X matched by M) is a base in B_X , M_Y is a base in B_Y , and subject to this, the sum $w(M)+v_{X}(M_{X})+v_{Y}(M_{Y})$ is maximized. The weighted matroid intersection problem is a special case in which the matroid valuations are constant, so we only seek to maximize $w(M)$ subject to M_X is a base in B_X and M_Y is a base in B_Y.^[14] Murota presents a polynomial-time algorithm for this problem.^[15]

Related Research Articles

The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows:

In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets or flats. In the language of partially ordered sets, a finite simple matroid is equivalent to a geometric lattice.

In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set $of vertices such that for every two vertices in, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening.$

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. Finding a matching in a bipartite graph can be treated as a network flow problem.

In combinatorics, a greedoid is a type of set system. It arises from the notion of the matroid, which was originally introduced by Whitney in 1935 to study planar graphs and was later used by Edmonds to characterize a class of optimization problems that can be solved by greedy algorithms. Around 1980, Korte and Lovász introduced the greedoid to further generalize this characterization of greedy algorithms; hence the name greedoid. Besides mathematical optimization, greedoids have also been connected to graph theory, language theory, order theory, and other areas of mathematics.

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most $k$ different colors, for a given value of $k$ , or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

In graph theory, a complete coloring is a vertex coloring in which every pair of colors appears on at least one pair of adjacent vertices. Equivalently, a complete coloring is minimal in the sense that it cannot be transformed into a proper coloring with fewer colors by merging pairs of color classes. The achromatic number $ψ(G)$ of a graph $G$ is the maximum number of colors possible in any complete coloring of $G$ .

<span class="mw-page-title-main">Dominating set</span> Subset of a graphs nodes such that all other nodes link to at least one

In graph theory, a dominating set for a graph $G$ is a subset $D$ of its vertices, such that any vertex of $G$ is either in $D$ , or has a neighbor in $D$ . The domination number $γ(G)$ is the number of vertices in a smallest dominating set for $G$ .

<span class="mw-page-title-main">Jack Edmonds</span> American/Canadian mathematician and computer scientist

Jack R. Edmonds is an American-born and educated computer scientist and mathematician who lived and worked in Canada for much of his life. He has made fundamental contributions to the fields of combinatorial optimization, polyhedral combinatorics, discrete mathematics and the theory of computing. He was the recipient of the 1985 John von Neumann Theory Prize.

In combinatorics, a branch of mathematics, a weighted matroid is a matroid endowed with function with respect to which one can perform a greedy algorithm.

In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete. This means that the decision problem cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems.

In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of $vertices from an n -vertex graph can partition the graph into disjoint subgraphs each of which has at most vertices.$

<span class="mw-page-title-main">Maximum cut</span> Problem of finding a maximum cut in a graph

For a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets $S$ and $T$ , such that the number of edges between $S$ and $T$ is as large as possible. Finding such a cut is known as the max-cut problem.

In matroid theory, the dual of a matroid $is another matroid that has the same elements as, and in which a set is independent if and only if has a basis set disjoint from it.$

In graph theory, the blossom algorithm is an algorithm for constructing maximum matchings on graphs. The algorithm was developed by Jack Edmonds in 1961, and published in 1965. Given a general graph $G = (V, E)$ , the algorithm finds a matching $M$ such that each vertex in $V$ is incident with at most one edge in $M$ and $| M |$ is maximized. The matching is constructed by iteratively improving an initial empty matching along augmenting paths in the graph. Unlike bipartite matching, the key new idea is that an odd-length cycle in the graph (blossom) is contracted to a single vertex, with the search continuing iteratively in the contracted graph.

In mathematics, a partition matroid or partitional matroid is a matroid that is a direct sum of uniform matroids. It is defined over a base set in which the elements are partitioned into different categories. For each category, there is a capacity constraint - a maximum number of allowed elements from this category. The independent sets of a partition matroid are exactly the sets in which, for each category, the number of elements from this category is at most the category capacity.

In mathematics and computer science, a matroid oracle is a subroutine through which an algorithm may access a matroid, an abstract combinatorial structure that can be used to describe the linear dependencies between vectors in a vector space or the spanning trees of a graph, among other applications.

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.

In the mathematical theory of matroids, the rank of a matroid is the maximum size of an independent set in the matroid. The rank of a subset S of elements of the matroid is, similarly, the maximum size of an independent subset of S, and the rank function of the matroid maps sets of elements to their ranks.

In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by Lawler (1976) as a common generalization of graph matching and matroid intersection. It is also known as polymatroid matching, or the matchoid problem.

References

1 2 Edmonds, Jack (1970), "Submodular functions, matroids, and certain polyhedra", in R. Guy; H. Hanam; N. Sauer; J. Schonheim (eds.), Combinatorial structures and their applications (Proc. 1969 Calgary Conference), Gordon and Breach, New York, pp. 69–87. Reprinted in M. Jünger et al. (Eds.): Combinatorial Optimization (Edmonds Festschrift), LNCS 2570, pp. 1126, Springer-Verlag, 2003.
↑ Lawler, Eugene L. (1975), "Matroid intersection algorithms", Mathematical Programming, 9 (1): 31–56, doi:10.1007/BF01681329, S2CID 206801650
↑ Iri, Masao; Tomizawa, Nobuaki (1976). "An Algorithm for Finding an Optimal "Independent Assignment"". 日本オペレーションズ・リサーチ学会論文誌. 19 (1): 32–57. doi: 10.15807/jorsj.19.32 .
↑ Frank, András (1981), "A weighted matroid intersection algorithm", Journal of Algorithms, 2 (4): 328–336, doi:10.1016/0196-6774(81)90032-8
↑ Orlin, James B.; VandeVate, John; Management, Sloan School of (2012-06-07). "On a "primal" matroid intersection algorithm".{{cite journal}}: Cite journal requires |journal= (help)
↑ Cunningham, William H. (1986-11-01). "Improved Bounds for Matroid Partition and Intersection Algorithms". SIAM Journal on Computing. 15 (4): 948–957. doi:10.1137/0215066. ISSN 0097-5397.
1 2 Brezovec, Carl; Cornuéjols, Gérard; Glover, Fred (1986), "Two algorithms for weighted matroid intersection", Mathematical Programming, 36 (1): 39–53, doi:10.1007/BF02591988, S2CID 34567631
↑ Huang, Chien-Chung; Kakimura, Naonori; Kamiyama, Naoyuki (2019-09-01). "Exact and approximation algorithms for weighted matroid intersection". Mathematical Programming. 177 (1): 85–112. doi:10.1007/s10107-018-1260-x. hdl: 2324/1474903 . ISSN 1436-4646. S2CID 254138118.
↑ Ghosh, Sumanta; Gurjar, Rohit; Raj, Roshan (2022-01-01), "A Deterministic Parallel Reduction from Weighted Matroid Intersection Search to Decision", Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, Society for Industrial and Applied Mathematics, pp. 1013–1035, doi:10.1137/1.9781611977073.44, ISBN 978-1-61197-707-3, S2CID 245799113 , retrieved 2022-11-28
↑ Bérczi, Kristóf; Király, Tamás; Yamaguchi, Yutaro; Yokoi, Yu (2022-09-28). "Matroid Intersection under Restricted Oracles". arXiv: 2209.14516 [cs.DS].
↑ Welsh, D. J. A. (2010) [1976], Matroid Theory, Courier Dover Publications, p. 131, ISBN 9780486474397 .
↑ Lawler, Eugene L. (1976), "Chapter 9: The Matroid Parity Problem", Combinatorial Optimization: Networks and Matroids, New York: Holt, Rinehart and Winston, pp. 356–367, MR 0439106 .
↑ Jensen, Per M.; Korte, Bernhard (1982), "Complexity of matroid property algorithms", SIAM Journal on Computing , 11 (1): 184–190, doi:10.1137/0211014, MR 0646772 .
↑ Murota, Kazuo (1996-11-01). "Valuated Matroid Intersection I: Optimality Criteria". SIAM Journal on Discrete Mathematics. 9 (4): 545–561. doi:10.1137/S0895480195279994. ISSN 0895-4801.
↑ Murota, Kazuo (November 1996). "Valuated Matroid Intersection II: Algorithms". SIAM Journal on Discrete Mathematics. 9 (4): 562–576. doi:10.1137/S0895480195280009. ISSN 0895-4801.