Transcript matchings

Perfect Matchings in
Bipartite Graphs
An undirected graph
G=(UV,E) is bipartite if
UV= and EUV.
A 1-1 and onto function
f:UV is a perfect
matching if for any uU,
(u,f(u))E.
1
Finding Perfect Matchings is
Easy
Matching as a flow
problem
2
What About Counting Them?
 Let A=(a(i,j))1i,jn be the
adjacency matrix of a bipartite
graph G=({u1,...,un}{v1,...,vn},E),
i.e. -
1 (u i , v j )  E
a(i, j )  
0 otherwise
 The number of perfect
matchings in the graph is
n
per ( A)   a(i, (i ))

permanent
i 1
sum over the permutations of {1,...,n}
1

1
1

0

1 0 0

1 0 1
0 1 0

1 0 1 
3
Cycle-Covers
• Given an undirected bipartite graph
G=({u1,...,un}{v1,...,vn},E), the corresponding
directed graph is G’=({w1,...,wn},E), where
(wi,wj)E iff (ui,vj)E.
• Definition: Given a directed graph
G=(V,E), a set of node-disjoint cycles that
together cover V is called a cycle-cover of
G.
• Observation: Every perfect matching in G
corresponds to a cycle-cover in G’ and viceversa.
4
Three Ways To View Our
Problem
1) Counting the number of Perfect
Matchings in a bipartite graph.
2) Computing the Permanent of a 0-1
matrix.
3) Counting the number of Cycle-Covers
in a directed graph.
5
#P - A Complexity Class of
Counting Problems
• LNP iff there is a polynomial time
decidable binary relation
s.t.
someR,
polynomial
x  L  y |y|  p(| x |)  R( x, y)
• f #P iff f(x)=| { y | R(x,y) } | where R is a
relation associated with some NP problem.
• We say a #P function is #P-Complete, if
every #P function Cook-reduces to it.
• It is well known that #SAT (i.e - counting
the number of satisfying assignments) is #PComplete.
6
On the Hardness of
Computing the Permanent
Claim [Val79]: Counting the number of cyclecovers in a directed graph is #P-Complete.
Proof: By a reduction from #SAT to a
generalization of the problem.
7
The Generalization:
Integer Permanent
 Activity: an integer weight
attached to each edge
(u,v)E, denoted (u,v).
 The activity of a matching M
is (M)=(u,v)M(u,v).
 The activity of a set of
matchings S is
(M)=MS(M).
 The goal is to compute the
total activity.
2
3
1
2
 2 3 0


0 0 1
 0 2 0


2
3
2
1
8
Integer Permanent Reduces to
0-1 Permanent
We would have loved to do
something of this sort...
the rest of the graph
1
12
9
Integer Permanent Reduces to
0-1 Permanent
So instead we do:
the rest of the graph
10
But this is really
cheating!
The integers may be
exponentially large, but we are
forbidden to add an exponential
number of nodes!
11
The Solution
the rest of the graph
...
12
What About Negative
Numbers?
 W.l.og, let us assume the only
negative numbers are -1’s.
 We can reduce the problem to
calculating the Permanent modulo (big
enough) N of a 0-1 matrix by replacing
each -1 with (N-1).
 Obviously, Perm mod N is efficiently
reducible to calculating the
13
Permanent.
Continuing With The
Hardness Proof
 We showed that computing the
permanent of an integer matrix
reduces to computing the permanent
of a 0-1 matrix.
 It remains to prove the reduction
from #SAT to integer Permanent.
 We start by presenting a few
gadgets.
14
The Choice Gadget
Observation: in any
cycle-cover the two
nodes must be covered
by either the left cycle
(true) or the right
cycle (false).
x= true
x= false
15
The Clause Gadget
Observation:
 no cycle-cover of this
graph contains all
three external edges.
 However, for every
proper subset of the
external edges, there
is exactly one cyclecover containing it.
each external edge
corresponds to one
literal
16
The Exclusive-Or Gadget
 The Perm. of the whole
matrix is 0.
 The Perm. of the matrix
resulting if we delete the
first (last) row and column
is 0.
 The Perm. of the matrix
resulting if we delete the
first (last) row and the
last (first) column is 4.
-1
-1
-1
 0 1  1  1


1 1 1 1 
0 1 1
2


0 1
3 0 

2
3
17
Plugging in the XOR-Gadget
Observe a cycle-cover of the graph with a
XOR-gadget plugged as in the below
figure.
 If e is traversed but not t (or vice
versa), the Perm. is multiplied by 4.
 Otherwise, the Perm. is added 0.
e
t
18
Putting It All Together
 One choice
gadget for
every
variable.
 One Clause
gadget for
every clause.
if the
literal is x
x= true
x= false
if the
literal is x
x= true
x= false
19
Sum Up
 Though finding a perfect matching in
a bipartite graph can be done in
polynomial time,
 counting the number of perfect
matchings is #P-Complete, and hence
believed to be impossible in
polynomial time.
20