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 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 and are independent sets, with , then there exists an element such that 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 an 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 ).
Algorithms The matroid parity problem for linear matroids can be solved by a randomized algorithm in time , where is the number of elements of the matroid, is its rank (the size of the largest independent set), and 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 . Without using fast matrix multiplication, the linear matroid parity problem can be solved in time . 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 .
These algorithms are based on a linear algebra formulation of the problem by . Suppose that an input to the problem consists of pairs of -dimensional vectors (arranged as column vectors in a matrix of size ). Then the number of pairs in the optimal solution is
where is a block diagonal matrix whose blocks are submatrices of the form
for a sequence of variables . The Schwartz–Zippel lemma can be used to test whether this matrix has full rank or not (that is, whether the solution has size or not), by assigning random values to the variables and testing whether the resulting matrix has determinant zero. By applying a greedy algorithm that removes pairs one at a time by setting their variables 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 pairs.
For graphic matroids, more efficient matroid parity algorithms are known, based on range searching data structures, with running time on graphs with vertices and edges. For simple graphs, is , but for multigraphs, it may be larger, so it is also of interest to have algorithms with smaller or no dependence on and worse dependence on . In these cases, it is also possible to solve the graphic matroid parity problem in randomized expected time , or in time when each pair of edges forms a path.
The matroid parity problem is NP-hard for certain compactly-represented matroids. Additionally, it requires more than a polynomial number of steps in the matroid oracle model, in which an algorithm is given access to an arbitrary matroid only through a subroutine that determines whether a given set is independent. Nevertheless, in these cases, 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 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 , it suffices to choose to be approximately .
Applications Many other optimization problems can be formulated as linear matroid parity problems, and solved in polynomial time using this formulation.
Graph matching
A maximum matching in a graph is a subset of edges, no two sharing an endpoint, that is as large as possible. It can be formulated as a matroid parity problem in a partition matroid that has an element for each vertex-edge incidence in the graph. In this matroid, two elements are paired if they are the two incidences for the same edge as each other. A subset of elements is independent if it has at most one incidence for each vertex of the graph. The pairs of elements in a solution to the matroid parity problem for this matroid are the incidences between edges in a maximum matching and their endpoints. Conversely, any matroid parity problem on a partition matroid can be interpreted as a maximum matching problem on a graph whose vertices correspond to the sets of the partition and whose edges correspond to the paired elements of the parity problem. Because matching can be solved in polynomial time, so can matroid parity problems on partition matroids.
Matroid intersection
An instance of the matroid intersection problem consists of two matroids on the same set of elements; the goal is to find a subset of the elements that is as large as possible and is independent in both matroids. To formulate matroid intersection as a matroid parity problem, construct a new matroid whose elements are the disjoint union of two copies of the given elements, one for each input matroid. In the new matroid, a subset is independent if its restriction to each of the two copies is independent in each of the two matroids, respectively. Pair the elements of the new matroid so that each element is paired with its copy. The pairs of elements in a solution to the matroid parity problem for this matroid are the two copies of each element in a solution to the matroid intersection problem.
Large planar subgraphs
In an arbitrary graph, the problem of finding the largest set of triangles in a given graph, with no cycles other than the chosen triangles, can be formulated as a matroid parity problem on a graphic matroid whose elements are edges of the graph, with one pair of edges per triangle (duplicating edges if necessary when they belong to more than one triangle). The pairs of elements in a solution to the matroid parity problem for this matroid are the two edges in each triangle of an optimal set of triangles.
The same problem can also be described as one of finding the largest Berge-acyclic sub-hypergraph of a 3-uniform hypergraph. A hypergraph is a structure analogous to a graph but allowing more than two vertices per hyperedge. A hypergraph whose hyperedges are the triangles of the given graph has exactly three vertices per edge, making it 3-uniform. There are multiple incompatible definitions of cycles in hypergraphs; a Berge cycle is a cyclic sequence that alternates between vertices and hyperedges, without repeated vertices or hyperedges, and with each consecutive pair of a vertex and hyperedge incident to each other. For any Berge cycle in the hypergraph of triangles, the same cyclic sequence of vertices would form a cycle in the underlying graph. Thus, finding a largest set of hyperedges with no Berge cycle is the same thing as finding the largest set of triangles in the corresponding graph that has no cycle other than the selected triangles themselves.
A cactus graph is a graph in which each two cycles have at most one vertex in common. As a special case, the graphs in which each cycle is a triangle are necessarily cactus graphs. The largest triangular cactus in the given graph can then be found by adding additional edges from a spanning tree, without creating any new cycles, so that the resulting subgraph has the same connected components as the original graph. Cactus graphs are automatically planar graphs, and the problem of finding triangular cactus graphs forms the basis for the largest known approximation ratio for the problem of finding the largest planar subgraph of a given graph, an important step in planarization. The largest triangular cactus always has at least 4/9 the number of edges of the largest planar subgraph, improving the 1/3 approximation ratio obtained by using an arbitrary spanning tree.
Combinatorial rigidity
A framework of rigid bars in the Euclidean plane, connected at their endpoints at flexible joints, can be fixed into its given position in the plane by fixing the positions of some of its joints, pinning them in place. A set of joints that, when pinned down, make the framework infinitesimally rigid is called a pinning set. Infinitesimal rigidity disallows even infinitesimally small rigid motions. It is, in general, a stronger condition than being unable to move, but the two concepts are the same when the initial placement of the framework is in a suitably generic position. The size of the smallest pinning set is the pinning number of the framework.