Matching polytope

<h2 id="preliminaries">Preliminaries</h2>
<h3>Incidence vectors and matrices</h3>
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 <a href="/facts/Incidence_matrix/eMXGWQBw">incidence matrix</a> 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 <a href="/facts/Triangle_graph/Ws7RAQKN">triangle graph</a> (a cycle of length 3), a square graph (a cycle of length 4), and the complete graph on 4 vertices.

<table><tbody><tr><td> ( 1 1 0 1 0 1 0 1 1 )   ,   ( 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 )   ,   ( 1 1 0 0 1 0 0 1 1 0 0 1 0 0 1 1 1 0 1 0 0 1 0 1 ) {\displaystyle {\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}}} </td></tr></tbody></table>
<h3>Linear programs</h3>
For every subset F of edges, the <a href="/facts/Dot_product/tNz8MLjT">dot product</a> 1E(v) · 1F represents the number of edges in F that are adjacent to v. Therefore, the following statements are equivalent:

<ul><li>A subset F of edges represents a <a href="/facts/Matching_(graph_theory)/s0pUJ7hd">matching</a> in G;</li>
<li>For every node v in V: 1E(v) · 1F ≤ 1.</li>
<li>AG · 1F ≤ 1V.</li></ul>
The cardinality of a set F of edges is the <a href="/facts/Dot_product/tNz8MLjT">dot product</a> 1E · 1F . Therefore, a <a href="/facts/Maximum_cardinality_matching/oKaChmBt">maximum cardinality matching</a> in G is given by the following <a href="/facts/Integer_linear_program/MDaaadoA">integer linear program</a>: <blockquote>Maximize 1E · x
Subject to: x in {0,1}m

 __________ AG · x ≤ 1V.</blockquote>
<h2 id="fractional-matching-polytope">Fractional matching polytope</h2>
The fractional matching polytope of a graph G, denoted FMP(G), is the polytope defined by the <a href="/facts/Relaxation_(approximation)/C2XdJ67N">relaxation</a> of the above linear program, in which each x may be a fraction and not just an integer:<blockquote>Maximize 1E · x
Subject to: x ≥ 0E

__________ AG · x ≤ 1V.</blockquote>This is a <a href="/facts/Linear_program/GduXFQxT">linear program</a>. It has m "at-least-0" constraints and n "less-than-one" constraints. The set of its feasible solutions is a <a href="/facts/Convex_polytope/2pRHcRgC">convex polytope</a>. Each point in this polytope is a <a href="/facts/Fractional_matching/falpEsoc">fractional matching</a>. For example, in the <a href="/facts/Triangle_graph/Ws7RAQKN">triangle graph</a> there are 3 edges, and the corresponding linear program has the following 6 constraints: <blockquote>Maximize x1+x2+x3
Subject to: x1≥0, x2≥0, x3≥0.

__________ x1+x2≤1, x2+x3≤1, x3+x1≤1.</blockquote>This set of inequalities represents a polytope in R3 - the 3-dimensional <a href="/facts/Euclidean_space/R2UbzmzM">Euclidean space</a>.
The polytope has five corners (<a href="/facts/Extreme_point/szg0j6an">extreme points</a>). 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).<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> 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 <a href="/facts/Fractional_matching/falpEsoc">fractional matching</a> 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.

<h2 id="integral-matching-polytope">Integral matching polytope</h2>
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:

<ul><li>The MP of the triangle graph is strictly contained in its FMP, since the MP does not contain the non-integral corner (1/2, 1/2, 1/2).</li>
<li>The MP of the 4-cycle graph is identical to its FMP, since all the corners of the FMP are integral.</li></ul>
<h2 id="the-matching-polytopes-in-a-bipartite-graph">The matching polytopes in a bipartite graph</h2>
The above example is a special case of the following general theorem:<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>: 274 <blockquote>G is a <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite graph</a> if-and-only-if MP(G) = FMP(G) if-and-only-if all corners of FMP(G) have only integer coordinates.</blockquote>This theorem can be proved in several ways.
<h3>Proof using matrices</h3>
When G is bipartite, its incidence matrix AG is <a href="/facts/Totally_unimodular/J6bRTkN4">totally unimodular</a> - every square submatrix of it has <a href="/facts/Determinant/eGYqJ2TF">determinant</a> 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:

<ul><li>If K has a column consisting only of zeros, then det K = 0.</li>
<li>If K has a column with a single 1, then det K can be expanded about this column and it equals either +1 or -1 times a determinant of a (k − 1) by (k − 1) matrix, which by the induction assumption is 0 or +1 or −1.</li>
<li>Otherwise, each column in K has two 1s. Since the graph is bipartite, the rows can be partitioned into two subsets, such that in each column, one 1 is in the top subset and the other 1 is in the bottom subset. This means that the sum of the top subset and the sum of the bottom subset are both equal to 1E minus a vector of |E| ones. This means that the rows of K are linearly dependent, so det K = 0.</li></ul>
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 <a href="/facts/Cramer%2527s_rule/aUt4Cena">Cramer's rule</a>, the solution is a <a href="/facts/Rational_number/VJQmyY05">rational number</a> 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).

<h2 id="the-facets-of-the-matching-polytope">The facets of the matching polytope</h2>
A <a href="/facts/Facet_(geometry)/IreRHGJ7">facet of a polytope</a> 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:<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>: 275–279 

<ul><li>x ≥ 0E</li>
<li>1E(v) · x ≤ 1 (where v is a non-isolated vertex such that, if v has only one neighbor u, then {u,v} is a connected component of G, and if v has exactly two neighbors, then they are not adjacent).</li>
<li>1E(S) · x ≤ (|S| − 1)/2 (where S spans a 2-connected <a href="/facts/Factor-critical_graph/CT2eT98n">factor-critical</a> subgraph.)</li></ul>
<h2 id="perfect-matching-polytope">Perfect matching polytope</h2>
The perfect matching polytope of a graph G, denoted PMP(G), is a polytope whose corners are the incidence vectors of the integral <a href="/facts/Perfect_matching/LmtRYLgK">perfect matchings</a> in G.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>: 274  Obviously, PMP(G) is contained in MP(G); In fact, PMP(G) is the face of MP(G) determined by the equality:<blockquote>1E · x = n/2.</blockquote><a href="/facts/Jack_Edmonds/4bLnep3e">Edmonds</a><a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> proved that, for every graph G, PMP(G) can be described by the following constraints:<blockquote>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.

x ≥ 0E</blockquote>Using this characterization and <a href="/facts/Farkas_lemma/FFvJdekz">Farkas lemma</a>, it is possible to obtain a good characterization of graphs having a perfect matching.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>: 206  By solving <a href="/facts/Algorithmic_problems_on_convex_sets/wVtJDwNQ">algorithmic problems on convex sets</a>, one can find a minimum-weight perfect matching.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>: 206--208 
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Stable_matching_polytope/DrAGeVIx">Stable matching polytope</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://math.mit.edu/~goemans/18438F09/lec6.pdf">The matching polytope, by Michael Goemans</a></li>
<li><a href="https://theory.stanford.edu/~jvondrak/CS369P/lec5.pdf">The matching polytope, by Jan Vondrak</a></li>
<li><a href="http://www.lix.polytechnique.fr/~vjost/mpri/non-bip-matching-polytope">The matching polytope, by Vincent Jost</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549 <a href="0-444-87916-1" target="_blank">0-444-87916-1</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">"1 Bipartite Matching Polytope, Stable Matching Polytope x1 x2 x3 Lecture 10: Feb ppt download". slideplayer.com. Retrieved 2020-07-17. <a href="https://slideplayer.com/slide/5120421/" target="_blank">https://slideplayer.com/slide/5120421/</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549 <a href="0-444-87916-1" target="_blank">0-444-87916-1</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549 <a href="0-444-87916-1" target="_blank">0-444-87916-1</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549 <a href="0-444-87916-1" target="_blank">0-444-87916-1</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Edmonds, Jack (January 1965). "Maximum matching and a polyhedron with 0,1-vertices" (PDF). Journal of Research of the National Bureau of Standards, Section B. 69B (1 and 2): 125. doi:10.6028/jres.069B.013. ISSN 0022-4340. <a href="https://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p125_A1b.pdf" target="_blank">https://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p125_A1b.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419 <a href="978-3-642-78242-8" target="_blank">978-3-642-78242-8</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419 <a href="978-3-642-78242-8" target="_blank">978-3-642-78242-8</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
</ol>

Matching polytope open-in-new

Matching polytope