In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid, a structure that abstracts and generalizes the notion of linear independence in vector spaces. 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. Matroid parity can be solved in polynomial time for linear matroids. However, it is NP-hard for certain compactly-represented matroids, and requires more than a polynomial number of steps in the matroid oracle model. Applications of matroid parity algorithms include finding large planar subgraphs and finding graph embeddings of maximum genus. Matroid parity algorithms can also be used to find connected vertex covers and feedback vertex sets in graphs of maximum degree three.
Formulation
A matroid can be defined from a finite set of elements and from a nonempty family of independent sets, subject to the following constraints:
Every subset of an independent set must be independent. If S {\displaystyle S} and T {\displaystyle T} are independent sets, with | T | > | S | {\displaystyle |T|>|S|} , then there exists an element t ∈ T {\displaystyle t\in T} such that S ∪ { t } {\displaystyle S\cup \{t\}} is independent. Examples of matroids include the linear matroids (in which the elements are vectors in a vector space, with linear independence), the graphic matroids (in which the elements are edges in an undirected graph, independent when they contain no cycle), and the partition matroids (in which the elements belong to a family of disjoint sets, and are independent when they contain at most one element in each set). Graphic matroids and partition matroids are special cases of linear matroids. In the matroid parity problem, the input consists of a matroid together with a pairing on its elements, so that each element belongs to one pair. The goal is to find a subset of the pairs, as large as possible, so that the union of the pairs in the chosen subset is independent. In another seemingly more general variation, the allowable pairs form a graph rather than having only one pair per element, and the goal is to find as many disjoint pairs as possible so that their union is independent. However, this variation is equivalent: If an element appears in more than one pair, one could modify the matroid by making multiple copies of that element, with only one copy allowed in an independent set, and use different copies of the element in different pairs. Repeating this replacement for all elements that appear in more than one pair would produce a equivalent instance of the matroid parity problem with each element belonging to only one pair. This problem was originally formulated in 1976 by Eugene Lawler. It generalized two previously-studied problems, graph matching and matroid intersection (see § Applications).
Algorithms The matroid parity problem for linear matroids can be solved by a randomized algorithm in time O ( n r ω − 1 ) {\displaystyle O(nr^{\omega -1})} , where n {\displaystyle n} is the number of elements of the matroid, r {\displaystyle r} is its rank (the size of the largest independent set), and ω {\displaystyle \omega } is the exponent in the time bounds for fast matrix multiplication. In particular, using a matrix multiplication algorithm of Virginia Vassilevska Williams et al., it can be solved in time O ( n r 1.3716 ) {\displaystyle O(nr^{1.3716})} . Without using fast matrix multiplication, the linear matroid parity problem can be solved in time O ( n r 2 ) {\displaystyle O(nr^{2})} . For instances with real numbers assigned as the weights of each element, it is also possible to find a minimum-weight solution to the matroid parity problem, or a maximum-weight paired independent set, in linear matroids, in time O ( n 3 r ) {\displaystyle O(n^{3}r)} . These algorithms are based on a linear algebra formulation of the problem by Geelen & Iwata (2005). Suppose that an input to the problem consists of m {\displaystyle m} pairs of r {\displaystyle r} -dimensional vectors (arranged as column vectors in a matrix M {\displaystyle M} of size r × 2 m {\displaystyle r\times 2m} ). Then the number of pairs in the optimal solution is
1 2 rank ( 0 M M T T ) − m , {\displaystyle {\frac {1}{2}}\operatorname {rank} {\begin{pmatrix}0&M\\M^{T}&T\end{pmatrix}}-m,}
… excerpt ends here. Continue reading the full article.
