IE 511 (Spring 2023)
Lecture Notes: : Matchings
Rasoul Etesami
Definition 1. Given an undirected graph G = (V, E), a matching is a subset of edges M ⊆ E
which meets each node at most once.
The IP formulation for max-cardinality matching is max{∑e∈E xe : Ax ≤ 1, x ∈ {0,1}|E|} where
A is the node-edge incidence matrix of the graph G = (V, E). We saw earlier that for bipartite
graphs, A is TU so the extreme points of {x ∈ R|E|+ ,Ax ≤ 1} are precisely the feasible matchings.
However, when G contains odd cycles, this polyhedron may have fractional extreme points and
we cannot simply solve the LP relaxation to obtain max-cardinality matching.
1 Maximum-Cardinality Matching over General Graphs
Definition 2. Given a graph and a matching M , a path in G is said to be alternating relative to
M if its edges alternate between M and E\M . A node v is said to be exposed relative to M if no
edge of M meets v. A path in G is augmenting relative to M if it is alternating and both of its
end points are exposed.
Theorem 3. Given a graph G = (V, E), a matching M in G is not maximum if and only if there
exists an augmenting path relative to M .
Proof: First let us assume that there exists an augmenting path relative to M with edge set E′.
Let M ′ = M∆E′, where ∆ denotes the symmetric difference between two sets. Then M ′ is also
a matching such that |M ′| = |M |+ 1. This shows that M is not maximum. Now assume that
M is not a maximum matching. Therefore, there exists a bigger matching M ′ with |M ′|> |M |.
Consider the set of edges D = M∆M ′. Now consider the graph G(D) = (V,D) with the edge set
D. The degree of each node in G(D) is either 0,1, or 2. Thus the connected components of G(D)
are disjoint paths and cycles. In particular, since the edges alternate between M and M ′, all the
cycles have even length as they contain the same number of edges from M and M ′. The paths
can contain either an even or odd number of edges. As |M ′|> |M |, one of the paths must contain
more edges from M ′ than from M . This path is an augmenting path with respect to M . □
Remark 4. Based on the above theorem, to find a maximum cardinality matching, at each step
we need to find an augmented path and increase the size of the matching along that path.
Definition 5. Given a matching M , a walk v0, v1, . . . , vt is an M−alternating walk if exactly one
of the edges (vi−1, vi) and (vi , vi+1) belong to M for every i = 1, . . . , t − 1.
Definition 6. An M−flower is an M−alternating walk v0, v1, . . . , vt such that: i) v0 is exposed,
ii) v0, v1, . . . , vt−1 are distinct, and iii) t is odd and vt = vi for some even index i < t (i.e. an
even length M−alternating path attached to an odd alternating cycle). The odd cycle (vi , . . . , vt)
in this M−flower is called an M−blossom and the vertex vi is called the base of the blossom.
Remark 7. In a blossom, every vertex u has an even length alternating path to the base vertex.
1
IE 511 (Spring 2023) Lecture Notes:: Matchings
Definition 8. Let B ⊆ V. The graph G\B obtained from contracting the node set B is the graph
where B is contracted to a new vertex b with an edge between b and v ∈ V\B if and only if
there was an edge between v and one of the nodes in B in the original graph, i.e.
G\B = €V\B ∪ {b}, E[V\B]∪ (v, b) : ∃u ∈ B, v ∈ V\B with {u, v} ∈ E Š.
In particular, if M is a matching on G, we let M\B denote the image of M on the contracted
graph G\B.
Proposition 9. Let B be an M−blossom in G. Then M is a maximum cardinality matching in G
if and only if M\B is a maximum cardinality matching in G\B.
Proof: (⇒) SupposeM\B is not amaximummatching in G\B. Then there exists anM−augmenting
path P in G\B. If P does not travel through B, then P is already an M−augmenting path in
G which is a contradiction. Now suppose P traverses B. In this case P can be extended to an
M−augmenting in G using the base of the blossom B and the above remark.
□
Proposition 10. Let P = v0, v1, . . . , vt be the shortest M−alternating walk between two exposed
vertices v0 and vt . Then either P is an augmenting path or v0, v1, . . . , v j is an M−flower for some
j ≤ t.
Proof: Assume P is not an augmenting path. Thus the walk must cut itself. Let v j be the
first vertex such that v j = vi for some i < j. So v0, v1, . . . , v j−1 are distinct. Now the cycle
vi , vi+1, . . . , v j has an odd length, otherwise we could shortcut the walk by removing this cycle
to find a shorter M−alternating walk. Also the path v0, v1, . . . , vi has an even number of edges,
otherwise (vi−1, vi) /∈ M =⇒ (vi , vi+1) ∈ M =⇒ (vi+1, vi+2) /∈ M =⇒ · · · =⇒ (v j−1, v j) ∈ M .
This is a contradiction since now node vi will meet twomatching edges (vi , vi+1) and (v j−1, v j). □
Blossom Contraction Algorithm:Given a graph G = (V, E) andmatchingM , find aM−augmenting
path (if there is any) using the following steps and augment the matching over it:
1. Let X be the set of exposed vertices.
2. Find the shortest X − X M−alternating walk P (if there is any). If P is an M−augmenting
path, return P. Otherwise, let B be a blossom to the M−flower present in P. Contract B
to obtain G\B and M\B. Apply the algorithm recursively to G\B and M\B to obtain an
augmenting path Q in G\B. Use Proposition 9 to expand Q to an augmenting path in G. If
there does not exist an X − X M−alternating walk, stop, the matching is maximum.
Remark 11. One can transfer the problem of finding an X − X M−alternating walk on G to
finding a shortest length path on a directed bipartite graph. Let D = (V ∪ V ′,A) where V ′ is a
copy of V and
A=
¦
(u, v′) : uv ∈ E\M©∪ ¦(u′, v) : uv ∈ M©.
Then a shortest X − X alternating walk in G corresponds to a shortest X − X ′ directed path in D
where X ′ is the copy of X in V ′. This is because a shortest alternating walk in G does not use
an edge uv ∈ E more than twice, and if it uses this edge twice it is once from u to v, and once
from v to u (otherwise, we can shortcut and make the walk shorter). Therefore, the image of
this shortest walk is a shortest length path on D. The direction of this directed path reflects the
point of alternative edges of the walk. Note that finding a shortest X − X ′ directed path in D can
be done in polynomial time using dynamic programming.
2
IE 511 (Spring 2023) Lecture Notes:: Matchings
Remark 12. The correctness of the Blossom Shrinking Algorithm easily follows from the previous
propositions and one can show that its run time is at most O(|E||V |2). Thus one can find a
maximum cardinality matching in general graph G in O(|E||V |2).
2 Polyhedra Representation of Matchings
Finally, if instead of max-cardinality matching we want to find the max-weight matching over a
general graph G, i.e., solving max{cx : x is a feasible matching in G}, then we can consider the
polyhedral representation of the feasible matchings. In fact, it has been shown that the convex
hull of feasible matchings in G denoted by Pmat(G) is an integral polytope, and can be fully
characterized by adding odd set constraints to the degree constraints. More precisely, let
Pmat(G) := Conv
{x ∈ {0,1}|E| : ∑
j∈δ(i)
x i j ≤ 1,∀i ∈ V}
.
Then, we have:
Theorem 13. Pmat(G) =
¦
x ∈ R|E|+ :
∑
j∈δ(i)
x i j ≤ 1,∀i ∈ V, ∑{i, j}∈E[U] x i j ≤ |U |−12 ∀U ⊆ V, |U | odd©.
The above theorem shows that we can solve the max-weight matching problem given by
IP: max
¦
cx :
∑
j∈δ(i) x i j ≤ 1,∀i ∈ V, x ∈ {0,1}|E|
©
, using the LP relaxation max{cx : x ∈
Pmat(G)}. Although this LP relaxation has exponentially many constraints, however, if we can
solve the separation problem efficiently, we can solve the max-weight matching problem efficiently.
In the separation problem, we are given x∗ ∈ R|E|+ , and we want to either find U ⊆ V , |U | odd
so that
∑
{i, j}∈E[U] x∗i j >
|U |−1
2 or prove that no such U exist. It is known that this separation
problem can be solved efficiently using the min-odd cut problem by treating x∗ as weights on the
edges and finding a min-odd cut.
3 An Application to Metric STSP
An instance of the symmetric traveling salesman problem (STSP) with metric costs is given by
an undirected complete graph G = (V, E) and nonnegative edge costs that satisfy the triangle
inequality, i.e., for any three vertices i, j, k ∈ V , we have ci, j ≤ ci,k + ck, j.1 The goal is to find a
Hamiltonian tour (a tour that visits every vertex exactly once) of minimum edge cost.
Definition 14. An undirected graph is called Eulerian if the degree of each node is even.
Lemma 15. Every connected Eulerian graph can be represented by an Eulerian walk which
travels over each edge exactly once and returns to its origin
Proof: Choose any starting vertex v, and follow a walk of edges from that vertex until returning
to v. It is not possible to get stuck at any vertex other than v, because the even degree of all
vertices ensures that, when the walk enters another vertex w there must be an unused edge
leaving w. The walk formed in this way may not cover all the edges of the initial graph. As long
as there exists a vertex u that belongs to the current walk but that has adjacent edges not part of
the walk, start another walk from u, following unused edges until returning to u, and join the
walked formed in this way to the previous walk. Since we assume the original graph is connected,
repeating the previous step will exhaust all edges of the graph. □
1For instance, any set of points in Rd with standard Euclidean norm possesses this metric property.
3
IE 511 (Spring 2023) Lecture Notes:: Matchings
Lemma 16. Consider the complete graph G = (V, E) with metric edge costs ci, j , (i, j) ∈ E. Let
H = (V, E′), E′ ⊆ E be a connected Eulerian subgraph of G over the same vertex set V . Then one
can find a Hamiltonian tour in G with cost no more than the cost of the Eulerien subgraph H.
Proof: Since H = (V, E′) is a connected Eulerian graph, using Lemma 15, it can be represented
using an Eulerian walk which visits the vertices in an order v0, v1, . . . , vt = v0, for some t. Let
vik , k = 1,2, . . . ,n, be the kth distinct vertex to be visited in this order. Clearly, vi1 , vi2 , . . . , vin , vi1
is a Hamiltonian tour in G. Moreover, using the metric property, the cost of this Hamiltonian
tour is at most the cost of the Eulerian walk, because
Cost of the Hamiltonian tour=
n∑
k=1
cvik ,vik+1 ≤
n∑
k=1
ik+1∑
j=ik+1
cv j ,v j+1 = Cost of the Eulerian walk,
where by convention we set in+1 = i1. □
A Heuristic Algorithm for STSP:
1. In the complete graph G = (V, E), find a minimum cost spanning tree T = (V, ET ) with
edge set ET .
2. Let V ′ ⊂ V be the set of odd degree nodes in the tree T . Consider the induced complete
graph G[V ′] on the nodes V ′, and find a minimum cost perfect matching M in G[V ′]. Add
the matching edges M to T to form an Eulerian subgraph (V, ET ∪M).
3. Use Lemma 16 to convert the Eulerian subgraph (V, ET ∪M) into a tour of no more cost.
Theorem 17. Let zc be the cost of the Hamiltoniam tour returned by the above algorithm and z
be the cost of the optimal Hamiltonian tour to STSP. Then, zc ≤ 32z.
Proof: Let zT =
∑
e∈ET ce be the cost of the min-cost spanning tree T = (V, ET ). Clearly,
zT ≤ z since every tour contains a spanning tree. Let us denote the optimal tour of length
z by 1,2, . . . ,n, 1, and let V ′ = { j1 < j2 < . . . < j2k} be the set of odd-degree nodes in T .
Consider two perfect matchings in G[V ′]: M1 =
{ j1, j2}, { j3, j4}, . . . , { j2k−1, j2k} of cost zM1 ,
and M2 =
{ j2, j3}, { j4, j5}, . . . , { j2k−2, j2k−1}, { j2k, j1} of cost zM2 . If we let zM be the cost of the
min-cost matching in G[V ′], we have zM ≤ zM1 and zM ≤ zM2 . Using triangle inequality, we have
2zM ≤ zM1 + zM2 = c j1, j2 + c j2, j3 + . . .+ c j2k , j1 ≤ c1,2 + c2,3 + c3,4 + . . .+ cn−1,n + cn,1 = z.
Therefore, by adding M to T , we obtain an Eulerian subgraph (V, ET ∪ M) whose cost is
zT + zM ≤ z + z2 = 32z. Finally, using Lemma 16, this Eulerian subgraph can be converted into a
Hamiltonian tour of no more cost, i.e., zc ≤ zT + zM ≤ 32z. □