Matchings in Graphs

Jan-May 2010

Schedule, and Lecture notes (unedited)

(See also some edited notes, topic-wise.)

#:Date	Lecturer	Scribe	Topic
1: 6 Jan	Meena	Rajesh	Definitions and examples. Finding maximum matching in bipartite graphs: the Hopcroft-Karp path augmentation algorithm.
2: 13 Jan	Meena	Nitin	Finding maximum matching in general graphs: Edmonds' blossom shrinking algorithm.
3: 21 Jan	Meena	Nitin, Rajesh	Tutte's theorem and Berge's formula for witness sets. Finding maximum matching in general graphs: a structural algorithm, and the Gallai-Edmonds structure theorem.
4: 28 Jan	Meena	Rajesh, Prajakta	Completing the structural algorithm description. Finding maximum matchings using linear programming. The bipartite polytope.
			Homework 1, due on 11 Feb
5: 4 Feb	Meena	Prajakta	The matching polytope in non-bipartite graphs.
6: 11 Feb	Prajakta	Jose	Stable matchings
7: 18 Feb	Prajakta	Karteek	Randomized NC algorithms: Tutte's theorem, Lovasz's observation using Schwarz-Zippel, Mulmuley-Vazirani-Vazirani isolation lemma and construction.
25 Feb	-	-	No class. (CMI mid-sem week)
8: 4 Mar	Jose	Meena	Graphs with a polynomial bound on the number of perfect matchings: decision, search, enumeration in P and NC.
9: 11Mar	Nitin	Meena	Unique bipartite matchings in NC.
			Homework 2, due on 25 Mar.
18 Mar	-	-	No class. (IMSc seminar week.)
10: 25 Mar	Rajesh	Meena	Popular matchings
11: 1 April	Meena	Nitin	Matchings in n^{omega} randomized time: the algebraic way
12: 8 Apr	Meena	Jose	Maintaining maximum matchings dynamically
13: 15 Apr	Meena; Yadu	Jose; Meena	Dynamic matchings continued; Counting planar perfect matchings via Pfaffians
14: 22 Apr	Meena	Neeldhara	Planar bipartite graphs: constructing a perfect matching in NC
			Homework 3, due on 29 April.

Sources

• 1. Matching Theory. L Lovasz and M Plummer, AMS vol 367.
• 2. Fast Parallel Algorithms for Graph Matching Problems. M Karpinski and W Rytter, OUP.
• 3. Geometry of Linear and Integer Optimization, Andreas Paffenholz, Discrete Maths III (BMS) 2008/09, FU Berlin.
• Santosh Vempala's Combinatorial Optimization course
• Atri Rudra's Algorithms course blog, lec 3-6.
• R W Irving. An efficient algorithm for the stable roommates problem. Journal of Algorithms Vol 6, 577-595, 1985.
• Mulmuley, Vazirani, Vazirani. "Matching is as easy as matrix inversion". Combinatorica (vol. 7, issue 1, 1987, pages 105-113)

Edited notes, topic-wise

• Hopcroft-Karp algorithm for maximum machings in bipartite graphs
• Edmonds' blossom-shrinking algorithm
• The Gallai-Edmonds decomposition, and a structural algorithm for maximum matching.
• The matching polytopes
  Notes + proof of last claim
• Stable matchings.
• Matchings in randomized NC: the Mulmuley-Vazirani-Vazirani algorithm.
• The Grigoriev-Karpinski deterministic NC algorithm when the number of perfect matchings is bounded by a polynomial.
• The Deterministic NC algorithm for testing unique perfect matching.
• Popular matchings.
• Matchings in $O(n^\omega)$ randomized time.
• Maintaining maximum matchings dynamically.
• Counting planar perfect matchings.
• Constructing a planar bipartite perfect matching in NC.