Transcript Slides

Algebraic Structures and Algorithms
for Matching and Matroid Problems
Nick Harvey
Perfect Matching
• Given graph G=(V,E)
• Perfect matching is M⊆E
such that each vertex
incident with exactly
one edge in M
Matching History
Dense Graphs
m=n2
Edmonds ’65
Blossom Alg.
O(n42)m)
Micali-Vazirani ’80-’90
Blossoms + “Blocking Flow”
O(n
)
O(√n2.5m)
Mucha-Sankowski ’04
Fast Matrix Multiplication
) )
O(n2.38
(n = # vertices, m = # edges)
non-trivial
non-trivial!
(<2.38 is exponent for matrix multiplication)
• All are
• Mucha
Mucha-Sankowski
uses sophisticated
’05: “[Our] algorithm
is quite complicated and
dynamic
connectivity
data structures
et al. ’01)It
heavily
relies
on graph theoretic
results and(Holm
techniques.
to maintain
partition”
(Cheriyan
’97)
would
be nice“canonical
to have a strictly
algebraic,
and
possibly
simpler, matching algorithm”.
Matching Algorithms
Dense Graphs
m=n2
Edmonds ’65
Blossom Alg.
O(n4)
Micali-Vazirani ’80-’90
Blossoms + “Blocking Flow”
O(n2.5)
Mucha-Sankowski ’04* Fast Matrix Multiplication
O(n2.38)
This Work*
O(n2.38)
Purely Algebraic,
Clean Divide-and-Conquer,
Fast Matrix Multiplication
• Conceptually simple
• Implemented in ~200 lines of MATLAB
* Randomized, but Las Vegas via [Cheriyan ’97]
(Linear) Matroid Intersection
• Find largest set of columns S such that
AS and BS are both linearly independent
A=
B=
1
1
0
0
7
9
3
1
1
0
0
1
6
2
3
4
1
0
1
0
6
9
4
8
0
1
1
1
3
2
7
4
1
1
0
1
7
4
0
2
0
1
1
0
1
9
4
2
1
0
1
1
9
6
3
5
0
1
0
1
0
1
3
3
AS
BS
Matroid Intersection
• Find largest set of columns S such that
AS and BS are both linearly independent
• Why?
• Many problems are a special case:
– Bipartite matching
– Arboresence (directed spanning tree), …
• Powerful tool:
– Bounded-Degree Sp. Tree [Goemans ’06]
Matroid Intersection History
Edmonds ’65-’70, Lawler ’75 Augmenting Paths
O(mn2) oracle
Cunningham ’86
“Blocking Flows”
O(mn2 log n)
Gabow-Xu ’89-’96
“Blocking Flows” &
Fast Matrix Mult.
O(mn1.62)
(for matrices of size n x m)
Matroid Intersection History
Edmonds ’65-’70, Lawler ’75 Augmenting Paths
O(mn2) oracle
Cunningham ’86 *
“Blocking Flows”
O(mn2 log n)
Gabow-Xu ’89-’96 *
“Blocking Flows” &
Fast Matrix Mult.
O(mn1.62)
This paper * †
Purely Algebraic,
Fast Matrix Mult.
1.38)
O(mn-1
)
• Essentially optimal:
– Best known alg to compute rank takes O(mn-1)
– Computing rank reduces to matroid intersection
* Assumes matroids are linear
† Randomized, and assumes matroids can be
represented over same field
Generic Matching Algorithm
For each e  E
If e is contained in a perfect matching
Add e to solution
Delete endpoints of e
Else
Delete edge e
Generic Matching Algorithm
For each e  E
If e is contained in a perfect matching
Add e to solution
Delete endpoints of e
Else
Delete edge e
• How can we test this?
• Randomization and linear algebra play key role
Matching Outline
• Implementing Generic Algorithm
– Tutte Matrix & Properties
– Rabin-Vazirani Algorithm
– Rank-1 Updates
– Rabin-Vazirani with Rank-1 Updates
– Our Recursive Algorithm (overview)
– Our Recursive Algorithm (fast updates)
Matching & Tutte Matrix
• Let G=(V,E) be a graph
• Define variable x{u,v} {u,v}∈E
• Define a skew-symmetric matrix T s.t.
Tu,v =
± x{u,v}
if {u,v}∈E
0
otherwise
0
a
x{a,b}
b
c
-x{a,b} -x{a,c}
0
x{a,c} x{b,c}
-x{b,c}
0
Properties of Tutte Matrix
Lemma [Tutte’47]: G has a perfect matching
iff T is non-singular.
Lemma [RV’89]: G[ V\{u,v}] has a perfect
matching iff (T-1)u,v  0.
Properties of Tutte Matrix
Lemma [Tutte’47]: G has a perfect matching
iff T is non-singular.
Lemma [RV’89]: G[ V\{u,v}] has a perfect
matching iff (T-1)u,v  0.
u
(T-1)u,v  0
v
Properties of Tutte Matrix
Lemma [Tutte’47]: G has a perfect matching
iff T is non-singular.
Lemma [RV’89]: G[ V\{u,v}] has a perfect
matching iff (T-1)u,v  0.
(T-1)u,v  0
G[ V\{u,v}] has
perfect
matching
Properties of Tutte Matrix
Lemma [Tutte’47]: G has a perfect matching
iff T is non-singular.
Lemma [RV’89]: G[ V\{u,v}] has a perfect
matching iff (T-1)u,v  0.
(T-1)u,v  0
G[ V\{u,v}] has
perfect
matching
Properties of Tutte Matrix
Lemma [Tutte’47]: G has a perfect matching
iff T is non-singular.
Lemma [RV’89]: G[ V\{u,v}] has a perfect
matching iff (T-1)u,v  0.
u
G[ V\{u,v}] has
perfect
matching
(T-1)u,v  0
v
Properties of Tutte Matrix
Lemma [Tutte’47]: G has a perfect matching
iff T is non-singular.
Lemma [RV’89]: G[ V\{u,v}] has a perfect
matching iff (T-1)u,v  0.
Computing T-1 very slow: Contains variables!
Lemma [Lovász’79]: These results hold w.h.p.
if we randomly choose values for x{u,v}’s.
Matching Algorithm
Rabin-Vazirani ’89
(Takes O(n) time)
Compute T-1
For each {u,v}  E
If T-1u,v  0
Add {u,v} to matching
Recurse on G[ V\{u,v} ]
• Total time: O(n+1) time
• Natural question: Can we recompute
T-1 quickly in each iteration?
Matching Outline
– Tutte Matrix & Properties
– Rabin-Vazirani Algorithm
– Rank-1 Updates
– Rabin-Vazirani with Rank-1 Updates
– Our Recursive Algorithm (overview)
– Our Recursive Algorithm (fast updates)
Rank-1 Updates
• Let T be a n x n matrix
• T + uvT is called a rank-1 update of T
1 1 1
1
1 1
1
1
1
1
T
+
1
2
3
∙
1 2 3
n
u
vT
n
Rank-1 Updates
• Let T be a n x n matrix
• T + uvT is called a rank-1 update of T
1 1 1
1
1 1
1
1
1
1
T
+
1 2 3
2 4 6
3 6 9
n
2n
3n
n 2n 3n
n2
uvT
• Computing rank-1 update takes O(n2) time
Rank-1 Updates
• Let T be a n x n matrix
• T + uvT is called a rank-1 update of T
• Claim: If you modify one entry of T,
then T-1 is modified by a rank-1 update.
T=
T-1 =
Rank-1 Updates
• Let T be a n x n matrix
• T + uvT is called a rank-1 update of T
• Claim: If you modify one entry of T,
then T-1 is modified by a rank-1 update.
• Claim: If you delete O(1) rows and
columns of T then T-1 is affected by O(1)
rank-1 updates.
 T-1 can be updated in O(n2) time
Matching Outline
– Tutte Matrix & Properties
– Rabin-Vazirani Algorithm
– Rank-1 Updates
– Rabin-Vazirani with Rank-1 Updates
– Our Recursive Algorithm (overview)
– Our Recursive Algorithm (fast updates)
RV Algorithm + Rank-1 Updates
Mucha-Sankowski ’04
Compute T-1
For each {u,v}  E
If T-1u,v  0
Add {u,v} to matching
Update T-1
(via rank-1 updates)
Recurse on G[ V\{u,v} ]
• Total runtime: O(n3) time
• Can updates use Fast Matrix Multiplication?
– Bipartite graphs: Yes
– Non-bip. graphs: Yes, but non-trivial
[MS’04]
RV Algorithm + Rank-1 Updates
Mucha-Sankowski ’04
Compute T-1
For each {u,v}  E
If T-1u,v  0
Add {u,v} to matching
Update T-1
(via rank-1 updates)
Recurse on G[ V\{u,v} ]
• Total runtime: O(n3) time
• Can updates use Fast Matrix Multiplication?
New approach: An unusual recursion!
Matching Outline
– Tutte Matrix & Properties
– Rabin-Vazirani Algorithm
– Rank-1 Updates
– Rabin-Vazirani with Rank-1 Updates
– Our Recursive Algorithm (overview)
– Our Recursive Algorithm (fast updates)
New Recursive Approach
(Here c=4 parts)
• Partition into c parts {V1,…,Vc}
• For each pair of parts {Va,Vb}
– Recurse on G[Va ⋃ Vb]
(arbitrarily)
(arbitrary order)
New Recursive Approach
• Partition into c parts {V1,…,Vc}
• For each pair of parts {Va,Vb}
– Recurse on G[Va ⋃ Vb]
(arbitrarily)
(arbitrary order)
New Recursive Approach
• Partition into c parts {V1,…,Vc}
• For each pair of parts {Va,Vb}
– Recurse on G[Va ⋃ Vb]
(arbitrarily)
(arbitrary order)
New Recursive Approach
• Partition into c parts {V1,…,Vc}
• For each pair of parts {Va,Vb}
– Recurse on G[Va ⋃ Vb]
• Base case: 2 vertices
(arbitrarily)
(arbitrary order)
New Recursive Approach
• Partition into c parts {V1,…,Vc}
(arbitrarily)
• For each pair of parts {Va,Vb}
(arbitrary order)
– Recurse on G[Va ⋃ Vb]
• Base case: 2 vertices {u,v}
– If T-1u,v  0, add {u,v} to matching, update T-1
Recursion F.A.Q.
• Why not just recurse on G[ Va ]?
– Edges between parts would be missed
– Claim: Our recursion examines every
pair of vertices  examines every edge
• Why does algorithm work?
– It implements Rabin-Vazirani Algorithm!
• Isn’t this horribly slow?
– No: we’ll see recurrence next
• Partition into c parts {V1,…,Vc}
(arbitrarily)
• For each pair of parts {Va,Vb}
(arbitrary order)
– Recurse on G[Va ⋃ Vb]
• Base case: 2 vertices {u,v}
– If T-1u,v  0, add {u,v} to matching, update T-1
Final Matching Algorithm
If base case with 2 vertices {u,v}
If T-1u,v  0, add {u,v} to matching
Else
Partition into c parts {V1,…,Vc}
For each pair {Va,Vb}
Recurse on G[Va ⋃ Vb]
Apply updates to current subproblem
s = size of
subproblem
 c   
c  2 
R ( s )     R s   O    s 
 2

2
c


 
 

Final Matching Algorithm
If base case with 2 vertices {u,v}
If T-1u,v  0, add {u,v} to matching
Else
Partition into c parts {V1,…,Vc}
For each pair {Va,Vb}
Recurse on G[Va ⋃ Vb]
Apply updates to current subproblem
s = size of
subproblem
 c   
c  2 
R ( s )     R s   O    s 
 2

2
c


 
 

Final Matching Algorithm
If base case with 2 vertices {u,v}
If T-1u,v  0, add {u,v} to matching
Else
Partition into c parts {V1,…,Vc}
Assume:
For each pair {Va,Vb}
O(s) time
Recurse on G[Va ⋃ Vb]
Apply updates to current subproblem
s = size of
subproblem
 c   
c  2 
R ( s )     R s   O    s 
 2

2
c


 
 

Time Analysis
 c   
c  2 
R ( s )     R s   O    s 


2
2
c
   
 

• Basic Divide-and-Conquer
c


– If log     then R(n)  O(n )
c/2  2 
c
1

• Since log c / 2    2 
,
log c  1
 2
just choose c large enough!
c = 13 is large enough if  = 2.38
Handling Updates
T=
Handling Updates
u v
u
v
T=
• Delete vertices u and v
u v
u
v
T-1 =
Handling Updates (Naively)
u v
u
v
T=
u v
u
v
T-1 =
• Delete vertices u and v  clear rows / columns
• Causes rank-1 updates to T-1
• Algorithm still takes (n3) time
Matching Outline
– Tutte Matrix & Properties
– Rabin-Vazirani Algorithm
– Rank-1 Updates
– Rabin-Vazirani with Rank-1 Updates
– Our Recursive Algorithm (overview)
– Our Recursive Algorithm (fast updates)
Just-in-time Updates
u v
u
v
T-1 =
• Don’t update entire matrix!
• Just update parent in recursion tree
• Updates outside of parent are postponed
Postponed Updates
u v
u
v
T-1 =
• Accumulate batches of updates
• Claim: New updates can be applied with matrix
multiplication and inversion
Final Matching Algorithm
If base case with 2 vertices {u,v}
If T-1u,v  0, add {u,v} to matching
Else
Partition into c parts {V1,…,Vc}
For each pair {Va,Vb}
Recurse on G[Va ⋃ Vb]
Apply updates to current subproblem
Invariant: Before / after child subproblem,
parent’s submatrix is completely updated
 in every base case, T-1u,v is up-to-date!
Graph G
c
  children
 2
 
Just apply postponed updates
All edges chosen in base cases
Only take edges that can be extended to a
perfect matching in the whole graph.
This decision is possible because invariant
ensures that T-1u,v is up-to-date.
Matching Summary
• Can compute a perfect matching in
O(n) = O(n2.38) time
• Algorithm uses only simple randomization,
linear algebra and divide-and-conquer
• Easy to implement
• Extensions for:
(by existing techniques)
– maximum matchings
– Las Vegas
More Extensions
• Same philosophy applies to many
matching-like problems
capturing
problem
– Design matrix
“algebraic
structure”
capturing problem
– Design algorithm to test if element in OPT
– Design method to efficiently do updates
J
A
Matroid Intersection
J
O(mn-1) algorithm
x3
BT
x4
x5
x6
x7
x8
More Extensions
• Same philosophy applies to many
matching-like problems
– Design matrix
“algebraic
structure”
capturing problem
capturing
problem
Bipartite Matroid Matching
& Basic Path-Matching
O(n) algorithm
Open Problems
• Fast, deterministic methods to choose
values for indeterminates?
– Implications for Matching in NC
• Scaling algorithms for weighted problems?
• O(n2) algorithms for matching by
completely different techniques?
– e.g., via Karger-Levine randomized max flow