Graph Matching: Shmuel Wimer

Graph Matching
prepared and Instructed by

Shmuel Wimer
Eng. Faculty, Bar-Ilan University
March 2020 Graph Matching 1

Matching in Bipartite Graphs

A matching in an undirected
graph is a set of pairwise
disjoint edges.

A perfect matching consumes
(saturates) all ’s vertices. Also
called complete matching.

has perfect matchings. (why?)

has no perfect matchings. (why?)

has perfect matchings. (why?)

Maximum Matching
A maximal matching is obtained by iteratively enlarging
the matching with a disjoint edge until saturation.
A maximum matching is a matching of largest size. It is
necessarily maximal.

Given a matching , an -alternating path is alternating
between edges in and edges not in .

Let ’s end vertices be not in . Replacement of ’s edges
with produces a matching such that , called
-augmentation.
Maximum matching has no augmentation path. (why?)
Symmetric Difference:
𝐺
(𝑉 , 𝐸 )
𝐺 𝐻
(𝑉 ,𝐸 )
𝐻
∆ 𝐻 ≜ 𝐹(𝑉 ,𝐸 ⊕ 𝐸 )
𝐺 𝐺 𝐻

Symmetric difference is used also for matching.
If and are two matchings then .

Theorem. (Berge 1957) A matching in a graph is a
maximum matching iff has no -augmentation path.
Proof. Maximum ⇒ no -augmentation. As if would

have -augmentation path, could not be maximum.

For no -augmentation ⇒ maximum, suppose that is not

maximum. We construct an -augmentation.

Consider a matching , , and Let be the spanning
subgraph of with .

and are matchings so a vertex of has degree 2 at
most. has therefore only disjoint paths and cycles,
and cycles must be of even lengths. (why?)

Since there is an edge alternating path with more
edges of than , and consequently there is an
-augmentation in . ■
Hall’s Matching Conditions

applicants apply for jobs, . Each applicant applies for a
few jobs. Can all the jobs be assigned?

𝑋
𝑌

Denote the neighbors in of . is clearly necessary for a
matching saturating .

Theorem. (Hall 1935) If is bipartite then has a
bipartition matching saturating iff for all .

Proof. Sufficiency. Let be maximum and for each ,
there is . Let be not saturated. There exists therefore ,
not -saturated.

We will find contradicting the theorem’s hypothesis.
𝑋

𝑆 𝑢

𝑌 𝑇 =𝑁 (𝑆)


Let and be reachable from by -alternating paths. We
claim that matches with .

The paths reach by edges not in M and by ’s edges.
Since is maximum, there is no -augmentation paths, so
every vertex of is -saturated.

Every extends via to a vertex in . Also, is reached by
from , thus .

The matching between and implies .

In fact, . If there was an edge from to a vertex , it could
not be in , yielding an alternating path to ,
contradicting is maximum.

Therefore, , which is a contradiction of the theorem’s
hypothesis. ■

For , Hall’s Theorem is the Marriage Theorem, proved
originally by Frobenius in 1917, for a set of men and
women.

If also every man is compatible (mutual preference)
with women and vice versa, there exists a perfect
matching of compatible pairs (perfect matrimonial ).

Corollary. Every -regular bipartite graph () has a perfect
matching.

Proof. Let , be the bipartition. Counting edges from to
and from to yields => .

Showing that Hall’s Theorem conditions are satisfied is
sufficient, as a matching saturating () will be perfect.

Consider an arbitrary . The number of edges
connecting to is and those edges are incident to .

The total number of edges incident to is . There is
therefore .

We thus obtained , satisfying Hall’s Theorem sufficient
condition . ■
Min-Max Dual Theorems
Can something be said on whether a matching is
maximum when a complete matching does not exist?

Exploring all alternating paths to find whether or not
there is an -augmentation is expensive.
We rather consider a dual problem that answers it

efficiently.

Definition. A vertex cover of is a set of vertices
containing at least one vertex of all ’s edges. We say that
’s vertices cover ’s edges.

No two edges in a matching are covered by a single
vertex. The size of a cover is therefore bounded below
by the maximum matching size.
Exhibiting a cover and a matching of the same size will
prove that both are optimal.
Each bipartite graph possesses such min-max equality,
but general graphs not necessarily.
maximum
matching=2
minimum
cover=2,3

Theorem. (Kӧnig 1931, Egerváry 1931) If is bipartite, the
sizes of maximum matching and minimum vertex cover
are equal.

Proof. Let be a ’s vertex cover, and a ’s matching. There
is always .

Let be a minimum cover. We subsequently construct a
matching from such that .

Let and . Two bipartite subgraphs and are induced by
and , respectively.

If we construct a complete matching in of into and a
complete matching in of into , their union will be a
matching in of size , proving the theorem.

It is impossible to have an edge connecting with .
Otherwise, would not be a cover. Hence the matchings
in and are disjoint.
𝑈

𝑋

𝑅

’

𝐻
𝑌

𝑇


Showing that Hall’s Theorem conditions are satisfied by
and ’ will ensure that matchings saturating and exist.

Let and consider . If we could replace by in and obtain
a smaller vertex cover, contradicting being minimum.

Therefore and Hall’s Theorem conditions hold in . has
therefore a complete matching of into .

Same arguments
hold for ’. ■

Independent Sets in Bipartite Graphs

Definition. The independence number of a graph is
the maximum size of an independent vertex set.

of a bipartite graph does not
always equal the size of a
partite set.

Definition. An edge cover is an
edge set covering ’s vertices.

Notation : maximum size of independent set.
: maximum size of matching.

: minimum size of vertex cover.
: minimum size of edge cover.

In this notation the Kӧnig-Egerváry Theorem states that
for every bipartite graph , .

Since there are no edges between the vertices of an
independent set, the edge cover of the graph cannot be
smaller, and therefore .

We will also prove that for every bipartite graph
(without isolated vertices) .

Lemma. is an independent set iff is a vertex cover, and
hence ().

Proof. independence ⇒ there are no edges within , so
must cover all the edges. Conversely, covers all the
edges ⇒ no edges connecting two vertices of . ■

Theorem. (Gallai 1959) If has no isolated vertices, then .

Proof. Let be a maximum matching (). We can use it to
construct an edge cover of by adding an edge incident
to each of the unsaturated vertices, yielding edge cover
of size .

The smallest edge cover is a lower bound. Therefore, .

Conversely, let be a minimum edge cover (). cannot
contain cycles, nor paths of more than two edges.
(why?)

is therefore a collection of isolated star subgraphs.

There are vertices at star centers, anyway covered by
the peripheral. Thus .

The isolated star subgraphs yield a -size matching by
arbitrarily choosing one edge per star.

A maximum matching cannot be smaller than , thus All
in all, . ■

Corollary. (Kӧnig 1916) If is bipartite with no isolated
vertices, . (|maximum independent set| =|minimum
edge cover|).

Proof. By the last lemma there is . By Gallai Theorem
there is .

From Kӧnig-Egerváry Theorem (|maximum matching|
=|minimum vertex cover|), and follows. ■

Maximum Matching Algorithm
Augmentation-path characterization of maximum
matching inspires an algorithm to find it.
A matching is enlarged step-by-step, one edge at a time,
by discovering an augmentation path.
If an augmentation path is not found, we will show a
vertex cover of same size as the current matching.
Kӧnig-Egerváry Min-Max Theorem ensures that the
matching is maximum.

An iteration looks at -unsaturated vertices only at one
partite since an augmented path must have its two ends
on distinct partite.

We search for all -unsaturated vertices. Starting at an
unsaturated vertex , a tree of -alternating paths rooted
at is implied.

Starting with zero matching, applications of the
Augmentation Path Algorithm produce a maximum
matching.
x1
𝑈

x
⊂x
𝑋 x4 x5 x6 x1
𝑆=𝑈

x x x4 x5 x6
2 3 2 3
𝑀

y1 y2 y3 y4 y5 y6
𝑇

y1 y2 y3 y4 y5 y6
𝑈 ⊂𝑋

x1 x2 x3 x4 x5 x6
End of iteration.
New augmented matching.
y1 y2 y3 y4 y5 y6
x1 x2 x3 x4 x5 x6
𝑆

No augmentation found.
Max matching found.
𝑇y

y2 y3 y4 y5 y6
1

Algorithm (an iteration finding -augmentation path).
Input: , matching in , all -unsaturated vertices .

Initialization: , .

Iteration: If all is marked stop: is a maximum matching
and is a minimum cover.

Otherwise, select unmarked . Consider each such that .
If is unsaturated an -ugmentation path from to exists.
Augment .

Otherwise, is matched by with some . In that case add
to and to .

After exploring all edges incident to , mark and iterate.
■
Theorem. Repeated application of the Augmenting Path
Algorithm to a bipartite graph produces matching and a
cover of the same size.

Proof. Consider upon termination.
-alternating path from enters only via ’s edges, hence
there is a matching between and .

An -alternating path traverses from into along any
-unsaturated edge, thus .

Since the algorithm marks all before termination, there
could not be an unsaturated edge connecting to . is
therefore a vertex cover.

Upon termination is saturated by (otherwise
-augmentation occurs), hence is -matched to .

Since contained all the -unsaturated vertices, is
-saturated, but with edges not involved in . therefore
involves at least edges.

Hence . Since |matching| |covering| always, equality
and optimality follow.

Weighted Bipartite Matching

Maximum matching in bipartite graphs generalizes to
nonnegative weighted graphs. Missing edges are zero
weighted, so is assumed.

Example. A farming company has farms and plants .
The profit of processing in is . Farms and plants should
1:1 matched.

The government will pay the company to stop farm
production and to stop plant manufacturing.

If the company will not take the offer and and will
continue working.
What should the government offer to completely stop
the farms and plants ?

It must offer for all . The government also wishes to
minimize .

Definitions. Given an matrix , a transversal is a
selection of entries, one for each row and one for each
column.

Finding a transversal of with maximum weight sum is
called the assignment problem, a matrix formulation of
the maximum weighted matching problem, where we
seek a perfect matching maximizing .

The labels and cover the weights if for all .

The minimum weighted cover problem is to find a
cover minimizing the cost .
The maximum weighted matching and the minimum
weighted cover problems are dual.
They generalize the bipartite maximum matching and

minimum cover problem. (how ?)

Edges are assigned with weight , and cover uses labels .
Vertices receiving form the cover.

Lemma. If is a complete (perfect) matching in a
bipartite graph and is a cover, .
Furthermore, iff consists of edges such that . is then a
maximum weight matching and is a minimum weight
cover.

Proof. Since the edges of are disjoint, it follows from
the constraints that summation over all ’s edges yields .

If equality must hold for each of the summand.

Finally, since is bounded by , equality implies that both
must be optimal. ■
Weighted Bipartite Matching Algorithm
The relation between maximum weighted matching and
edge covered by equalities lends itself to an algorithm,
named the Hungarian Algorithm.

It combines -augmentation path with cover trimming.

Denote by the subgraph of spanned by the edges
satisfying .

The algorithm ensures that if has a perfect matching
(in , its weight is and by the lemma both matching and
cover are optimal.
Otherwise, the algorithm modifies the cover.

Algorithm. (Kuhn 1955, Munkres 1957)
Input: Bipartition and weights of .

Idea: Maintain a cover , iteratively reducing its cost, until
the equality graph has a perfect matching.

Initialization: Define a feasible labeling , and . Find a
maximum matching in (apply path augmentation to ).

Iteration: If is perfect in stop. is a maximum weight
matching by the lemma.

Else, let be the -unsaturated in and , and be reached
from by -alternating paths.
𝑈

𝑆− 𝜀 in
𝑋

𝜀
𝑌

𝑇 +𝜀

Let

Decrease by for all and increase by for all .

Derive a new equality graph . If it contains an
-augmentation path, replace by a maximum matching in
.
Iterate anyway. ■

𝑢 4 8 6

𝑢 4 8 6

𝑋
𝑋 𝑈

6 1 6 1
4 4
1 6 8 1 6 8
𝑌
𝑌

𝑣 0 0 0

𝑣 0 𝑀

0 𝐺𝑢 , 𝑣

0

𝑢 4 8 6

𝑋

𝑆

6 1 Minimum surplus from to :
4
1 6 8
𝑌

𝑀

𝑇

𝑣 0 0 𝐺𝑢 , 𝑣 0

𝑢 4 6 4
𝑢 4 6 4

𝑋
𝑋
6 1 6 1
4 4
1 6 8 1 6 8
𝑌

𝑌

𝑣 0 2 0

𝑣 0 𝐺 ′𝑢 , 𝑣

2 𝑀

0

which is a maximum in is a perfect matching in and
therefore it is maximum weight matching.
To validate, the total edge weight is 16, same as the
total cover.

Theorem. The Hungarian Algorithm finds a maximum
weight matching and a minimum cost cover.

Proof. The algorithm begins with a cover, each iteration
produces a cover, and termination occurs only when the
equality graph has a perfect matching in .

Consider the numbers , obtained from the cover , after
decreasing and increasing by . If and , then and cover
holds.

If and , then and cover holds.

If and , then , hence cover holds.

Finally, if and , then . Since was the smallest surplus
from to , cover holds.

The termination condition ensures that optimum is
achieved. It is required therefore to show that
termination occurs after a finite number of iterations.

First, never decreases since . If increases, great. If not,
then increases in .

That follows from the addition of a new cover-equal
edge between and , traversed in by an -alternating path
emanating from (-unsaturated). ■
Stable Matching
Preferences are optimized Instead of total weight.

A matching of men and women is stable if there is no
man-woman pair such that and prefer each other over
their current partners.
Otherwise the matching is unstable; and will leave their
current partners and will switch to each other.

Men: Women:

is stable.
Gale and Shapley proved that a stable matching always
exists and can be found by a simple algorithm.

Algorithm. (Gale-Shapley Proposal Algorithm).
Input: Preference ranking by each of men and women.
Idea: produce stable matching using proposals while

tracking past proposals and rejections.
Iteration: Each unmatched man proposes to the highest
woman on his list which has not yet rejected him.
If each woman receives one proposal stop. a stable

matching is obtained.
Otherwise, at least one woman receives at least two
proposals. Every such woman rejects all but the highest
on her list, to which she says “maybe”. ■
Theorem. (Gale-Shapley 1962) The Proposal Algorithm
produces stable matching.

Proof. The algorithm terminates (with some matching)
since at each nonterminal iteration at least one woman
rejects a man, reducing the list of potential mates.
Observation: the proposals sequence made by a man is

non increasing in his preference list, whereas the list of
“maybe” said by a woman is non decreasing in her list.
(Repeated proposals by a man to the same woman and
repeated “maybe” answers are possible, until rejected or
assigned.)

If matching is unstable, there is and mates, where 1:
prefers over and 2: prefers over .

1: Since on ’s preference list , proposed to before it
proposed to , a time where must have already been
rejected by .

2: By the observation, the “maybe” answer sequence
made by is non decreasing in its preferences. Since on ’s
list , could never propose to , hence a contradiction to 1.
■
Question: Which gender is happier using Gale-Shapley
Algorithm? (The algorithm is asymmetric.)
Once the choice of all men are distinct, they all get their
highest possible preference , whereas the women are
stuck with whomever proposed .
The precise statement of “the men are happier” is that if
we switch the role of men and women, each woman
winds up happy and each man winds up unhappy at
least as in the original proposal algorithm. (homework)

If women propose to men they get , which are their first
choices .
Of all stable matching, men are happiest by the male-
proposal algorithm whereas women are happiest by the
female-proposal algorithm. (homework)
Study the case where all men and all women have same
preference lists. (homework)
The algorithm can be used for assignments of new
graduates of medicine schools to hospitals.
Who is happier, young doctors or hospitals? Hospitals
are happier since they run hospital-proposal.
Hospitals started using it on early 50’s to avoid chaos,
ten years before Gale-Shapley algorithm was proved.
Matching in Arbitrary Graphs

We shall establish a lower bound on the uncovered
vertices of a maximum matching in a graph

Definition. An odd component of a graph is a
component of odd order (odd number of vertices).
is the number of odd components of a graph .

If is a matching in and is the uncovered vertices, each
odd component of must include at least one vertex not
covered by , hence .

This inequality can be extended to all induced
subgraphs of .

Let , and let be an odd component of . If is fully
covered by (all ’s vertices touched), there must be at
least one matching a vertex of .
odd

𝐺
odd odd
𝑀

𝑀

𝑀

𝐺−𝑆
even

𝑆 even

At most vertices of can be matched by with those of .

Consider the uncovered vertices of a matching in .
odd component

𝑀
𝑀

𝑈

At least odd components must have a vertex not
covered by , hence , for any .

𝐺−𝑆

𝐺
𝑆

Does have a perfect matching ?

, whereas , hence .

Claim. If it happens that for some matching and there is
, then is a maximum matching. (homework)

Such is called a barrier of and is a certificate that is
maximum.
¿𝑈 ∨≥2

is maximum
since .
𝑼

𝑴


The empty set is trivially a barrier of any graph
possessing a perfect matching since .
Any single vertex is also a barrier of any graph
possessing a perfect matching. (why?)
The empty set is a barrier of a graph for which a
deletion of one vertex results in a subgraph possessing
a perfect matching. (why?)
The union of barriers of the components of a graph is a
barrier of the graph. (homework)
Any minimum covering of a bipartite graph is a barrier.
(homework)

Definition: A factor of is a spanning subgraph of .
Definition: A -factor is a -regular (all vertices have
degree ) spanning subgraph. A perfect matching is
-factor.

Theorem. (Tutte’s 1-Factor Theorem 1947) A graph has
1-factor iff for every .

Proof (Lovász 1975). (Only if) Let have -factor (perfect
matching) and . -factor was shown before.

The proof of the opposite direction is more complex.
Tutte’s condition is preserved under edge addition,
namely, if , so it is for .

That follows since edge addition may merge two
components into one, hence .

Proof plan. We will consider a graph possessing Tutte’s
condition and assume in contrary that it has no 1-factor,
but the addition of any edge obtains 1-factor.
We then add two edge and construct a 1-factor in . We
then remove and show the existence of 1-factor in ,
hence a contradiction.

must be even. That follows by taking , so , hence no odd
component could exist.

Let be such that is connected to all s vertices and
suppose that consists of disjoint cliques.
𝐺 −𝑈

odd clique
𝑈
even clique

vertices are arbitrarily paired up, with the leftover
residing in the odd components. Since , the leftover ones
matched to any of .

is a clique of its own, hence all its rest vertices (even)
are paired up and 1-factor in exists.
We must therefore consider for the contradiction
establishment that is not made all of cliques.

There must be non-adjacent vertices sharing a
common vertex (otherwise are in a clique, or is an
independent set).
Since , there is , non adjacent to .

Recall that was chosen to be maximal not having 1-
factor, such that the addition of any edge will turn it to
possess 1-factor.

Let and be the 1-factors in and , respectively. By
maximality and .
It suffices to show that has 1-factor avoiding and , in
contradiction with the maximality of .

Consider with the edges of . There is .
Since the degree of any ’s vertex in and is exactly one
(perfect matchings), has only isolated vertices and
disjoint even cycles.

Let be the cycle in , . If , a 1-factor is established by ,
avoiding both and .
𝑀2
𝑀1 𝑦 𝑀

2
𝑤

If both , the following
cycle occurs. 𝑀

1
𝑀

1

Here is a matching of 𝑀

2 𝑥 𝑀

1 𝑧 𝑀

2
avoiding both and .
Outside either or 𝑀

2
𝑦 𝑤

edges are used,

yielding perfect 𝑀

1
matching in .
𝑀

2 𝑥 𝑧 𝑀 2


Application: Clock Gating Optimization
The clock signal (CLK) of flip-flops (FFs) is disabled if data
is unchanged.
k
O
X
D1
FF
Q1 CL D2
FF
Q2
clk_g
clk_g
D3
Latch Q3
A
clk

To minimize gating overhead, FFs are grouped in -size
sets for joint clock gating.

: FF group size (to optimize), : FF’s probability for .
Savings (dynamic capacitance) at single FF (gain, loss):
𝐶 latch

𝑘
𝐶 save ≥𝑞 ( 𝐶 FF+𝐶 wire ) − [𝑘
+ ( 1− 𝑞 ) ( 𝐶 wire +𝑐 OR ) ]

Derivate by :


Optimal -size Flip-flop Grouping

Given FFs operated (toggled) along clock cycles let be a
FF’s toggling vector, where ,

Let and be the toggling vectors of and , .
The number of redundant clock pulses occurred by

clocking jointly and is .

If , minimizing the redundant clock pulses turns to
finding min cost matching in weighted .
FF 𝑗

‖a 𝑖 ⊕ a 𝑗‖

FF𝑖

Optimal FF pairing () is solved in polynomial time by
minimal cost perfect matching.
Example: 8 FFs, 13 cycles min cost matching. Redundant
CLK occurs at 0.

What happens for ?
Is repetitive min cost matching optimal for ?
a 𝑘 ∨a𝑙

a 𝑖∨a 𝑗
FF𝑖
FF𝑘 FF 𝑗
FF𝑙


No! Here is the optimal 4-size grouping

Optimal -grouping is NP-hard

Problem. Let be a simple graph (no parallel edges and
loops) of vertices. Let the degree , . Show that has a
perfect matching.

Solution. If has no perfect matching, let be a largest
(maximum) possible matching.
Let . Since is not perfect and , there are at least two
unmatched vertices and edge does not exist.
Consider how and can be connected. Assume there
are at least 3 edges involved.

𝑢

𝑣

𝑢

𝑣

𝑥
𝑦
𝑥
𝑦

There are 2 independent edges which can be used for
matching if is removed, contradicting that is a largest
matching.
Consequently, cannot be both connected to any of the
vertices involved in , which number is at most .
Consequently, .
But , hence a contradiction.

Problem Denote by the size of the largest independent
set of . Show that the vertices of a graph can be
covered by no more than vertex-disjoint paths.

Proof: Let be a maximum independent set of , and let
be the maximum independent set of .
There is by construction.
Since and are independent sets, for any there is and .
Hence is bipartite, denoted .
𝑉𝑖

𝑉 𝑖+1


We show that the minimum vertex cover satisfies .
Firstly, for any there is . Otherwise would not be
maximal by its choice since it could be enlarged by
replacing by few vertices of .
Hence, the minimum vertex cover may consist of
vertices alone.
It must include all the vertices of , as otherwise could be
enlarged, hence not maximal by its choice. Consequently
.

By König’s theorem there is . Hence there is a matching
of into .
𝑉𝑖
𝑉 𝑖+1

consists of vertex-disjoint paths covering , except
vertices of .
Taking these as one-point paths, we obtain vertex-
disjoint paths covering

Graph Matching: Shmuel Wimer

Uploaded by

Copyright:

Available Formats

Graph Matching: Shmuel Wimer

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Graph Matching: Shmuel Wimer

Uploaded by

Copyright:

Available Formats

Graph Matching

prepared and Instructed by

March 2020 Graph Matching 1

March 2020 Graph Matching 2

March 2020 Graph Matching 4

have -augmentation path, could not be maximum.

maximum. We construct an -augmentation.

March 2020 Graph Matching 5

March 2020 Graph Matching 7

March 2020 Graph Matching 9

We rather consider a dual problem that answers it

March 2020 Graph Matching 12

March 2020 Graph Matching 14

March 2020 Graph Matching 15

March 2020 Graph Matching 16

March 2020 Graph Matching 18

March 2020 Graph Matching 19

March 2020 Graph Matching 20

March 2020 Graph Matching 21

March 2020 Graph Matching 24

March 2020 Graph Matching 26

March 2020 Graph Matching 27

They generalize the bipartite maximum matching and

March 2020 Graph Matching 36

March 2020 Graph Matching 38

Idea: produce stable matching using proposals while

If each woman receives one proposal stop. a stable

Observation: the proposals sequence made by a man is

March 2020 Graph Matching 47

March 2020 Graph Matching 48

March 2020 Graph Matching 49

March 2020 Graph Matching 50

March 2020 Graph Matching 56

edges are used,

March 2020 Graph Matching 57

Savings (dynamic capacitance) at single FF (gain, loss):

March 2020 Graph Matching 59

The number of redundant clock pulses occurred by

March 2020 Graph Matching 63

March 2020 Graph Matching 64

March 2020 Graph Matching 65

March 2020 Graph Matching 66

March 2020 Graph Matching 68

March 2020 Graph Matching 69

March 2020 Graph Matching 70

You might also like