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.
[1] The problem was formulated by Lawler (1976) as a common generalization of graph matching and matroid intersection.
[1][4] Applications of matroid parity algorithms include finding large planar subgraphs[5] and finding graph embeddings of maximum genus.
[6] Matroid parity algorithms can also be used to find connected dominating sets and feedback vertex sets in graphs of maximum degree three.
is the exponent in the time bounds for fast matrix multiplication.
[1] In particular, using a matrix multiplication algorithm of Virginia Vassilevska Williams et al.,[9] it can be solved in time
Without using fast matrix multiplication, the linear matroid parity problem can be solved in time
[1] 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
[10] These algorithms are based on a linear algebra formulation of the problem by Geelen & Iwata (2005).
[11] The Schwartz–Zippel lemma can be used to test whether this matrix has full rank or not (that is, whether the solution has size
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
[1] For graphic matroids, more efficient matroid parity algorithms are known, based on range searching data structures, with running time
, but for multigraphs, it may be larger, so it is also of interest to have algorithms with smaller or no dependence on
In these cases, it is also possible to solve the graphic matroid parity problem in randomized expected time
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
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 same problem can also be described as one of finding the largest Berge-acyclic sub-hypergraph of a 3-uniform hypergraph.
In the hypergraph version of the problem, the hyper-edges are the triangles of the given graph.
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.
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.
[5]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.
Infinitesimal rigidity 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.
(This is different from the notion of independence in the rigidity matroid of the graph, which has the rows of the same matrix as its elements.)
Therefore, a minimum pinning set can be found by complementing the solution to this matroid pairing problem.
This is a spanning tree with the property that, in the subgraph of edges not in the tree, the number of connected components with an odd number of edges is as small as possible.
In it, a subset of edges is independent if its removal does not separate the graph.
subsets of a larger set that satisfy a computable test.
, and applying Yao's principle relating expected and average-case complexity, 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.
