Matroid Parity Problem

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 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. These algorithms can also be used to find connected dominating sets 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 notion of what it means for subsets of elements to be independent, subject to the following constraints:
*Every subset of an independent set should be independent.
*If $S$ and $T$ are independent sets, with $, T, >, S,$, then there exists an element $t\in T$ such that $S\cup\$ 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. Another seemingly more general variation, in which the allowable pairs form a graph rather than having only one pair per element, is equivalent: an element appearing in more than one pair could be replaced by multiple copies of the element, one per pair.

Algorithms

The matroid parity problem for linear matroids can be solved by a randomized algorithm in time $O(nr^)$, where $n$ is the number of elements of the matroid, $r$ is its rank (the size of the largest independent set), and $\omega$ is the exponent in the time bounds for fast matrix multiplication.
In particular, using a matrix multiplication algorithm of Le Gall, it can be solved in time $O(nr^)$.
Without using fast matrix multiplication, the linear matroid parity problem can be solved in time $O(nr^2)$.

These algorithms are based on a linear algebra formulation of the problem by . Suppose that an input to the problem consists of $m$ pairs of $r$-dimensional vectors (arranged as column vectors in a matrix $M$ of size $r\times 2m$). Then the number of pairs in the optimal solution is

:$\frac\operatorname\begin0&M\\M^T&T\end -m,$

where $T$ is a block diagonal matrix whose blocks are $2\times 2$ submatrices of the form

:$\begin0&t_i\\-t_i&0\end$

for a sequence of variables $t_1,\dots t_m$. The Schwartz–Zippel lemma can be used to test whether this matrix has full rank or not (that is, whether the solution has size $r/2$ or not), by assigning random values to the variables $t_i$ and testing whether the resulting matrix has determinant zero. By applying a greedy algorithm that removes pairs one at a time by setting their indeterminates to zero as long as the matrix remains of full rank (maintaining the inverse matrix using the Sherman–Morrison formula to check the rank after each removal), one can find a solution whenever this test shows that it exists. Additional methods extend this algorithm to the case that the optimal solution to the matroid parity problem has fewer than $r/2$ pairs.

For graphic matroids, more efficient algorithms are known, with running time $O(mn\log^6 n)$ on graphs with $m$ vertices and $n$ edges.
For simple graphs, $m$ is $O(n^2)$, but for multigraphs, it may be larger, so it is also of interest to have algorithms with smaller or no dependence on $m$ and worse dependence on $n$. In these cases, it is also possible to solve the graphic matroid parity problem in randomized expected time $O(n^4)$, or in time $O(n^3)$ when each pair of edges forms a path.

Although the matroid parity problem is NP-hard for arbitrary matroids, it can still be approximated efficiently. Simple local search algorithms provide a polynomial-time approximation scheme for this problem, and find solutions whose size, as a fraction of the optimal solution size, is arbitrarily close to one. The algorithm starts with the empty set as its solution, and repeatedly attempts to increase the solution size by one by removing at most a constant number $C$ of pairs from the solution and replacing them by a different set with one more pair. When no more such moves are possible, the resulting solution is returned as the approximation to the optimal solution. To achieve an approximation ratio of $1-\epsilon$, it suffices to choose $C$ to be approximately $5^$.

Applications

Many other optimization problems can be formulated as linear matroid parity problems, and solved in polynomial time using this formulation.

Hardness

The clique problem, of finding a $k$-vertex complete subgraph in a given $n$-vertex graph $G$, can be transformed into an instance of matroid parity as follows.
Construct a paving matroid on $2n$ elements, paired up so that there is one pair of elements per pair of vertices. Define a subset $S$ of these elements to be independent if it satisfies any one of the following three conditions:
*$S$ has fewer than $2k$ elements.
*$S$ has exactly $2k$ elements, but is not the union of $k$ pairs of elements.
*$S$ is the union of $k$ pairs of elements that form a clique in $G$.
Then there is a solution to the matroid parity problem for this matroid, of size $2k$, if and only if $G$ has a clique of size $k$. Since finding cliques of a given size is NP-complete, it follows that determining whether this type of matrix parity problem has a solution of size $2k$ is also NP-complete.

This problem transformation does not depend on the structure of the clique problem in any deep way, and would work for any other problem of finding size-$k$ subsets of a larger set that satisfy a computable test. By applying it to a randomly-permuted graph that contains exactly one clique of size $k$, one can show that any deterministic or randomized algorithm for matroid parity that accesses its matroid only by independence tests needs to make an exponential number of tests.

References

{{reflist, refs=

{{citation
, last1 = Călinescu , first1 = Gruia
, last2 = Fernandes , first2 = Cristina G.
, last3 = Finkler , first3 = Ulrich
, last4 = Karloff , first4 = Howard
, doi = 10.1006/jagm.1997.0920
, issue = 2
, journal = Journal of Algorithms
, mr = 1622397
, pages = 269–302
, title = A better approximation algorithm for finding planar subgraphs
, volume = 27
, year = 1998, citeseerx = 10.1.1.47.4731
, s2cid = 8329680
.

{{citation
, last1 = Cheung , first1 = Ho Yee
, last2 = Lau , first2 = Lap Chi
, last3 = Leung , first3 = Kai Man
, doi = 10.1145/2601066
, issue = 3
, journal = ACM Transactions on Algorithms
, mr = 3233690
, pages = 10:1–10:26
, title = Algebraic algorithms for linear matroid parity problems
, url = https://cs.uwaterloo.ca/~lapchi/papers/parity.pdf
, volume = 10
, year = 2014, citeseerx = 10.1.1.194.604
, s2cid = 894004

{{citation
, last = Speckenmeyer , first = E.
, contribution = Bounds on feedback vertex sets of undirected cubic graphs
, mr = 875903
, pages = 719–729
, publisher = North-Holland , location = Amsterdam
, series = Colloquia Mathematica Societatis János Bolyai
, title = Algebra, Combinatorics and Logic in Computer Science, Vol. I, II (Győr, 1983)
, volume = 42
, year = 1986

{{citation
, last = Lawler , first = Eugene L. , authorlink = Eugene Lawler
, contribution = Chapter 9: The Matroid Parity Problem
, contribution-url = https://books.google.com/books?id=MTuoAAAAQBAJ&pg=PA356
, location = New York
, mr = 0439106
, pages = 356–367
, publisher = Holt, Rinehart and Winston
, title = Combinatorial Optimization: Networks and Matroids
, year = 1976

{{citation
, last1 = Furst , first1 = Merrick L.
, last2 = Gross , first2 = Jonathan L.
, last3 = McGeoch , first3 = Lyle A.
, doi = 10.1145/44483.44485
, issue = 3
, journal = Journal of the ACM
, mr = 963159
, pages = 523–534
, title = Finding a maximum-genus graph imbedding
, volume = 35
, year = 1988, s2cid = 17991210

{{citation
, last1 = Geelen , first1 = James , author1-link = Jim Geelen
, last2 = Iwata , first2 = Satoru
, doi = 10.1007/s00493-005-0013-7
, issue = 2
, journal = Combinatorica
, mr = 2127610
, pages = 187–215
, title = Matroid matching via mixed skew-symmetric matrices
, volume = 25
, year = 2005, citeseerx = 10.1.1.702.5431 , s2cid = 18576135

{{citation
, last1 = Gabow , first1 = Harold N. , author1-link = Harold N. Gabow
, last2 = Stallmann , first2 = Matthias
, editor-last = Brauer , editor-first = Wilfried
, contribution = Efficient algorithms for graphic matroid intersection and parity (extended abstract)
, doi = 10.1007/BFb0015746
, location = Berlin
, mr = 819256
, pages = 210–220
, publisher = Springer
, series = Lecture Notes in Computer Science
, title = 12th International Colloquium on Automata, Languages, and Programming (ICALP), Nafplion, Greece, July 15–19, 1985
, volume = 194
, year = 1985, isbn = 978-3-540-15650-5

{{citation
, last1 = Jensen , first1 = Per M.
, last2 = Korte , first2 = Bernhard , author2-link = Bernhard Korte
, doi = 10.1137/0211014
, issue = 1
, journal = SIAM Journal on Computing
, mr = 646772
, pages = 184–190
, title = Complexity of matroid property algorithms
, volume = 11
, year = 1982

{{citation
, last = Soto , first = José A.
, arxiv = 1102.3491
, doi = 10.1016/j.dam.2012.10.019
, issue = part 2
, journal = Discrete Applied Mathematics
, mr = 3159127
, pages = 406–412
, title = A simple PTAS for weighted matroid matching on strongly base orderable matroids
, volume = 164
, year = 2014

{{citation
, last = Le Gall , first = François
, contribution = Powers of tensors and fast matrix multiplication
, doi = 10.1145/2608628.2608664
, location = New York
, mr = 3239939
, pages = 296–303
, publisher = ACM
, title = Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC 2014)
, year = 2014, isbn = 9781450325011
, s2cid = 2597483

{{citation
, last = Lovász , first = L. , authorlink = László Lovász
, doi = 10.1016/0095-8956(80)90066-0
, issue = 2
, journal = Journal of Combinatorial Theory
, mr = 572475
, pages = 208–236
, series = Series B
, title = Matroid matching and some applications
, volume = 28
, year = 1980, doi-access = free

{{citation
, last1 = Lee , first1 = Jon
, last2 = Sviridenko , first2 = Maxim
, last3 = Vondrák , first3 = Jan
, doi = 10.1137/11083232X
, issue = 1
, journal = SIAM Journal on Computing
, mr = 3033132
, pages = 357–379
, title = Matroid matching: the power of local search
, volume = 42
, year = 2013, citeseerx = 10.1.1.600.4878

{{citation
, last1 = Ueno , first1 = Shuichi
, last2 = Kajitani , first2 = Yoji
, last3 = Gotoh , first3 = Shin'ya
, department = Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986)
, doi = 10.1016/0012-365X(88)90226-9
, issue = 1–3
, journal = Discrete Mathematics
, mr = 975556
, pages = 355–360
, title = On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
, volume = 72
, year = 1988, doi-access = free

Combinatorial optimization
Intersection