Matching polytope explained

In graph theory, the matching polytope of a given graph is a geometric object representing the possible matchings in the graph. It is a convex polytope each of whose corners corresponds to a matching. It has great theoretical importance in the theory of matching.

Preliminaries

Incidence vectors and matrices

Let G = (V, E) be a graph with n = |V| nodes and m = |E| edges.

For every subset U of vertices, its incidence vector 1U is a vector of size n, in which element v is 1 if node v is in U, and 0 otherwise. Similarly, for every subset F of edges, its incidence vector 1F is a vector of size m, in which element e is 1 if edge e is in F, and 0 otherwise.

For every node v in V, the set of edges in E adjacent to v is denoted by E(v). Therefore, each vector 1E(v) is a 1-by-m vector in which element e is 1 if edge e is adjacent to v, and 0 otherwise. The incidence matrix of the graph, denoted by AG, is an n-by-m matrix in which each row v is the incidence vector 1E(V). In other words, each element v,e in the matrix is 1 if node v is adjacent to edge e, and 0 otherwise.

Below are three examples of incidence matrices: the triangle graph (a cycle of length 3), a square graph (a cycle of length 4), and the complete graph on 4 vertices.

\begin{pmatrix} 1&1&0\\ 1&0&1\\ 0&1&1 \end{pmatrix} ~,~ \begin{pmatrix} 1&1&0&0\\ 0&1&1&0\\ 0&0&1&1\\ 1&0&0&1\\ \end{pmatrix} ~,~ \begin{pmatrix} 1&1&0&0&1&0\\ 0&1&1&0&0&1\\ 0&0&1&1&1&0\\ 1&0&0&1&0&1\\ \end{pmatrix}

Linear programs

For every subset F of edges, the dot product 1E(v) · 1F represents the number of edges in F that are adjacent to v. Therefore, the following statements are equivalent:

The cardinality of a set F of edges is the dot product 1E · 1F . Therefore, a maximum cardinality matching in G is given by the following integer linear program:

Maximize 1E · x

Subject to: x in m

__________ AG · x 1V.

Fractional matching polytope

The fractional matching polytope of a graph G, denoted FMP(G), is the polytope defined by the relaxation of the above linear program, in which each x may be a fraction and not just an integer:

Maximize 1E · x

Subject to: x0E

__________ AG · x 1V.

This is a linear program. It has m "at-least-0" constraints and n "less-than-one" constraints. The set of its feasible solutions is a convex polytope. Each point in this polytope is a fractional matching. For example, in the triangle graph there are 3 edges, and the corresponding linear program has the following 6 constraints:
Maximize x1+x2+x3

Subject to: x1≥0, x2≥0, x3≥0.

__________ x1+x2≤1, x2+x3≤1, x3+x1≤1.

This set of inequalities represents a polytope in R3 - the 3-dimensional Euclidean space.

The polytope has five corners (extreme points). These are the points that attain equality in 3 out of the 6 defining inequalities. The corners are (0,0,0), (1,0,0), (0,1,0), (0,0,1), and (1/2,1/2,1/2).[1] The first corner (0,0,0) represents the trivial (empty) matching. The next three corners (1,0,0), (0,1,0), (0,0,1) represent the three matchings of size 1. The fifth corner (1/2,1/2,1/2) does not represent a matching - it represents a fractional matching in which each edge is "half in, half out". Note that this is the largest fractional matching in this graph - its weight is 3/2, in contrast to the three integral matchings whose size is only 1.

As another example, in the 4-cycle there are 4 edges. The corresponding LP has 4+4=8 constraints. The FMP is a convex polytope in R4. The corners of this polytope are (0,0,0,0), (1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1), (1,0,1,0), (0,1,0,1). Each of the last 2 corners represents matching of size 2, which is a maximum matching. Note that in this case all corners have integer coordinates.

Integral matching polytope

The integral matching polytope (usually called just the matching polytope) of a graph G, denoted MP(G), is a polytope whose corners are the incidence vectors of the integral matchings in G.

MP(G) is always contained in FMP(G). In the above examples:

The matching polytopes in a bipartite graph

The above example is a special case of the following general theorem:

G is a bipartite graph if-and-only-if MP(G) = FMP(G) if-and-only-if all corners of FMP(G) have only integer coordinates.
This theorem can be proved in several ways.

Proof using matrices

When G is bipartite, its incidence matrix AG is totally unimodular - every square submatrix of it has determinant 0, +1 or −1. The proof is by induction on k - the size of the submatrix (which we denote by K). The base k = 1 follows from the definition of AG - every element in it is either 0 or 1. For k>1 there are several cases:

As an example, in the 4-cycle (which is bipartite), the det AG = 1. In contrast, in the 3-cycle (which is not bipartite), det AG = 2.

Each corner of FMP(G) satisfies a set of m linearly-independent inequalities with equality. Therefore, to calculate the corner coordinates we have to solve a system of equations defined by a square submatrix of AG. By Cramer's rule, the solution is a rational number in which the denominator is the determinant of this submatrix. This determinant must by +1 or −1; therefore the solution is an integer vector. Therefore all corner coordinates are integers.

By the n "less-than-one" constraints, the corner coordinates are either 0 or 1; therefore each corner is the incidence vector of an integral matching in G. Hence FMP(G) = MP(G).

The facets of the matching polytope

A facet of a polytope is the set of its points which satisfy an essential defining inequality of the polytope with equality. If the polytope is d-dimensional, then its facets are (d − 1)-dimensional. For any graph G, the facets of MP(G) are given by the following inequalities:

Perfect matching polytope

The perfect matching polytope of a graph G, denoted PMP(G), is a polytope whose corners are the incidence vectors of the integral perfect matchings in G. Obviously, PMP(G) is contained in MP(G); In fact, PMP(G) is the face of MP(G) determined by the equality:

1E · x = n/2.
Edmonds[2] proved that, for every graph G, PMP(G) can be described by the following constraints:
1E(v) · x = 1 for all v in V (-- exactly one edge adjacent to v is in the matching)

1E(W) · x ≥ 1 for every subset W of V with |W| odd (-- at least one edge should connect W to V\W). These constraints are called odd cut constraints.

x0E

Using this characterization and Farkas lemma, it is possible to obtain a good characterization of graphs having a perfect matching. By solving algorithmic problems on convex sets, one can find a minimum-weight perfect matching.

See also

References

  1. Web site: 1 Bipartite Matching Polytope, Stable Matching Polytope x1 x2 x3 Lecture 10: Feb ppt download. 2020-07-17. slideplayer.com.
  2. Edmonds . Jack . January 1965 . Maximum matching and a polyhedron with 0,1-vertices . Journal of Research of the National Bureau of Standards, Section B . en . 69B . 1 and 2 . 125 . 10.6028/jres.069B.013 . 0022-4340.

External links