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 is an example of a framework of bars connected at their endpoints that is not rigid with the two pinned joints marked with "x": it can still flex as shown with one
degree of freedom. 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. Any framework determines a
rigidity matrix having a row for each bar and two columns for each joint, one column for each of the joint's two coordinate dimensions. The nonzeros in the row for each edge lie in the columns for the edge's two endpoints, and equal the coordinate differences of the endpoints. This defines a linear matroid pairing problem in which the pairs of elements are the pairs of columns for each vertex, and in which a set of columns is independent if they are linearly independent as vectors. (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.) A set of paired columns is independent if and only if it comes from a set of joints that is complementary to a pinning set. Therefore, a minimum pinning set can be found by complementing the solution to this matroid pairing problem.
Maximum-genus embeddings whose complement has one odd component (red) A
cellular embedding of a given graph onto an
oriented surface of the maximum possible
genus can be obtained from a
Xuong tree of the graph. For this problem, a cellular embedding is a drawing of the graph on the surface, without crossings, so that the faces of the surface (the parts of the surface that would be obtained by cutting it along all of the edges of the graph) are topological disks. A surface is oriented if it does not contain a
Möbius strip. One way to describe a cellular embedding and the surface that it is embedded onto is to list, for each vertex of the graph, a
cyclic order of the edges incident to that vertex, in their clockwise ordering around the vertex on the surface. This information can be used to find the boundary of each face, by tracing it from vertex to vertex. The surface itself can then be recovered, up to topological equivalence, by gluing together a collection of disks, one for each boundary traced in this way. A Xuong tree 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. The optimal embedding can then be obtained by pairing edges within each component and inserting each pair into an embedding, one pair at a time. As a
base case for this insertion process, the Xuong tree itself is embedded onto a sphere (the only closed surface onto which it can be embedded), arbitrarily. Then, when adding each pair of remaining edges, there is a choice of how to add the edges into the cyclic orderings at their endpoints, and this choice can always be made in such a way that it increases the genus of the surface by one. The embedding resulting from this insertion process has the maximum genus possible. To formulate the problem of finding a Xuong tree as a matroid parity problem, first subdivide each edge e of the given graph into a path, with the length of the path equal to the number of other edges incident to e. Then, pair the edges of the subdivided graph, so that each pair of incident edges in the original graph is represented by a single pair of edges in the subdivided graph, and each edge in the subdivided graph is paired exactly once. Solve a matroid parity problem with the paired edges of the subdivided graph, using its cographic matroid. This is the
dual matroid of a graphic matroid. In it, a subset of edges is independent if its removal does not separate the graph. Any spanning tree of the original graph that avoids the edges used in the matroid parity solution is necessarily a Xuong tree. Each pair selected in the solution can be used to increase the genus of the embedding, so the total genus is the number of selected pairs.
Connected vertex cover A
connected vertex cover in a graph is a subset of vertices whose
induced subgraph is
connected and includes an endpoint of every edge of the whole graph. It is NP-hard to find the smallest connected vertex cover in arbitrary graphs, or even in
planar graphs of maximum degree four, but they can be found in polynomial time for graphs of maximum degree three. A simplified version of the algorithm applies to
cubic graphs, graphs with exactly three edges incident to each vertex. It forms a new graph with each vertex and edge of the given graph replaced by paths of two paired edges. For a vertex v of the given cubic graph, the three vertices of v's replacement path form the three endpoints of the paths that replace the three edges incident to v. A solution to the matroid parity problem for the cographic matroid of this path-replaced graph cannot use paths that replace edges, because removing the edges of this path would isolate the middle vertex of the path. Disconnecting this vertex violates the defining property of the cographic matroid that removing an independent set cannot disconnect the graph. Therefore, the solution must consist only of pairs of edges coming from vertices. More strongly, these pairs must come from vertices that form a non-separating independent set in the original graph. Any other paired edges would separate the expanded graph and form a dependent set in the cographic matroid. In any connected graph, the
complement of a maximum non-separating independent set is a minimum connected vertex cover. In a graph of maximum degree three, some simple additional transformations reduce the problem to one on a cubic graph.
Feedback vertex set A
feedback vertex set in a graph is a subset of vertices that touches all cycles. In connected cubic graphs, this problem is closely related to connected vertex covers: the size of the minimum feedback set is exactly c-n/2+1 where n is the number of vertices and c is the size of a connected vertex cover. The same expansion of each vertex and each edge into a two-edge path, used for connected vertex covers, produces an expanded graph with paired edges. The matroid parity problem on the graphic matroid has an optimal solution that includes all of the pairs coming from edges of the original graph, together with pairs coming from a set of vertices complementary to a feedback vertex set. Complementing the set of selected vertices produces a minimum feedback vertex set. Again, this solution can be extended from cubic graphs to graphs of maximum degree three. ==Hardness==