The course revolves around the problem of Perfect Matchings in graphs. The study of Perfect Matchings in computer science has been quite extensive and influential. It has been studied in a variety of different algorithmic models - sequential, parallel, bounded-space, randomized, online, approximation, counting etc. It has generated many ingenious ideas which also apply to much more general settings, e.g., the primal-dual LP algorithms, the Isolation Lemma. In fact, the notion of polynomial time as a measure of efficient computation arose in the context of perfect matchings. The aim of this course is to study perfect matchings in these various paradigms, pick up different ideas it inspires and to get introduced to open research problems around it.
Perfect matching and characterizing its existence, Linear programming formulations, Greedy algorithm, Polynomial time algorithms, Randomized Parallel algorithms, Exact matching, Primal-dual LP algorithms, Extended formulations for linear programs, Matrix Scaling algorithm, Approximating the Permanent, Online Algorithms, #P-hardness of counting, Efficient counting in planar graphs and minor-free graphs, Parallel algorithms in planar graphs, Derandomization, Approximate counting of bipartite matchings.
Tuesday, Friday 5:30 - 7 pm. CC101.
**
Lecture 0 (Jan 3): Introduction and course contents. Hall's theorem.
[1] Chapter 1
Combinatorials algorithms and Linear Programming
Lecture 1 (Jan 11): Proof of Hall's theorem. Greedy approximation algorithm. A polynomial time algorithm for bipartite matching via augmenting paths.
[1] Chapter 1, [2] Chapter 16
Lecture 2 (Jan 15): Linear programming formulation for bipartite matching.
[1] Chapter 7 [2] Chapter 18
Lecture 3 (Jan 18): Bipartite Vertex Cover LP formulation. Linear Programming Duality.
[2] Chapter 5
Lecture 4 (Jan 18): Primal-dual LP algorithm for weighted bipartite matching.
See these notes
Lecture 5 (Jan 21): Nonbipartite matching - Tutte's theorem.
[2] Chapter 24
Lecture 6 (Jan 28): Nonbipartite matching - augmenting path algorithm.
[2] Chapter 24
Lecture 7 (Feb 1): Nonbipartite matching polytope.
[2] Chapter 26
Lecture 8 (Feb 5): Nonbipartite matching polytope and LP dual.
[2] Chapter 26
Lecture 9 (Feb 5): Primal-dual algorithm.
[2] Chapter 26
Lecture 10 (Feb 8): Primal-dual algorithm.
[2] Chapter 26
Homework Problems up to Lecture 10
Algebraic Algorithms
Lecture 11 (Feb 12): Complexity class NC and some fundamental problems in NC.
A Parallel algorithm to compute determinant.
See this paper
Lecture 12 (Feb 15): Determinant continued. A randomized parallel algorithm for bipartite matching.
[4] Chapter 7
Lecture 13 (Feb 19): Bipartite matching in RNC. Decision: Schwartz-Zippel-Demillo-Lipton Lemma. Construction: isolating weight assignment.
[4] Chapter 7, Chapter 12.
Lecture 14 (Mar 1): Proof of Isolation Lemma. Algebraic proof of Hall's theorem. Tutte matrix for general graphs.
[4] Chapter 12. Section 6 in Edmonds' Paper
Lecture 15 (Mar 5): Tutte matrix and Pfaffian. Exact matching. Some applications of counting perfect matchings.
MVV Paper, [1] Chapter 8.
Lecture 16 (Mar 8): Counting in Bipartite Planar graphs.
[1] Chapter 8.
Lecture 17 (Mar 12): Counting in General Planar graphs. Derandomizing the Isolation Lemma for Bipartite Planar graphs.
[1] Chapter 8. DKR paper
Lecture 18 (Mar 15): Derandomizing the Isolation Lemma for Bipartite graphs.
paper
Other Topics
Lecture 19 (Mar 19): Bipartite Matching via Matrix Scaling.
paper
Lecture 20 (Mar 29): Linear Programming extended formulations: planar graphs.
paper
paper
Lecture 21 (April 2): Extendended formulations: planar graphs continued and Yannakakis's characterization.
Lecture 22 (April 5): Online Bipartite Matching: $(1-1/e)$-approximation for fractional matching (joint class with CS602).
Homework Problems for Lecture 11-onwards
Student Pressentations
April 9 : An algebraic proof of Tutte's Theorem by Kunal Mittal
An NC algorithm to find a perfect matching in bipartite planar graphs by Sahil Pandey
April 12 : 3/2-approximation of metric TSP via matching by Shourya Pandey
O(m \sqrt{n})-time algorithm for bipartite matching by Riya Baviskar
April 16 : Ellipsoid method for linear programming by Swapnam Bajpai
An RNC algorithm for perfect matching by Anand Radhakrishnan
April 17 : Max-cut in Planar Graphs via Perfect Matching by Chandra Kanta Mohapatra
April 19 : Counting the number of perfect matchings is #P-hard by Prasad
[1] Laszlo Lovasz and Michael D. Plummer. Matching Theory. North-Holland mathematics studies. Elsevier Science Ltd, 1986.
[2] Alexander Schrijver. Combinatorial optimization : polyhedra and efficiency. Springer- Verlag, Berlin, Heidelberg, New York, N.Y., et al., 2003
[3] Marek Karpinski and Wojciech Rytter. Fast Parallel Algorithms for Graph Matching Problems. Oxford University Press, 1998.
[4] Rajeev Motwani and Prabhakar Raghavan. Randomized algorithms, volume 28. ACM, New York, NY, USA, 1996
**