Meetings

Click on the theme item for the meeting plan for that theme.Click on the meeting item for references, exercises, and additional reading related to it.

**Theme 1 : Flows and Cuts in graphs**- 16 meetings- Meeting 01 : Mon, Jan 09, 11:00 am-11:50 am
- Meeting 02 : Tue, Jan 10, 10:00 am-10:50 am
- Meeting 03 : Wed, Jan 11, 09:00 am-09:50 am
- Meeting 04 : Thu, Jan 12, 12:00 pm-12:50 pm
- Meeting 05 : Mon, Jan 16, 11:00 am-11:50 am
- Meeting 06 : Tue, Jan 17, 10:00 am-10:50 am
- Meeting 07 : Wed, Jan 18, 09:00 am-09:50 am
- Meeting 08 : Thu, Jan 19, 12:00 pm-12:50 pm
- Meeting 09 : Mon, Jan 23, 11:00 am-11:50 am
- Meeting 10 : Tue, Jan 24, 10:00 am-10:50 am
- Meeting 11 : Wed, Jan 25, 09:00 am-09:50 am
- Meeting 12 : Thu, Jan 26, 12:00 pm-12:50 pm
- Meeting 13 : Mon, Jan 30, 11:00 am-11:50 am
- Meeting 14 : Tue, Jan 31, 10:00 am-10:50 am
- Meeting 15 : Wed, Feb 01, 09:00 am-09:50 am
- Meeting 16 : Thu, Feb 02, 12:00 pm-12:50 pm

Introduction to course contents, administrative announcements, TA introduction. <br> Max Flow problem definition, Min-cost Max flow problem definition. References Exercises Reading Introduction to course contents, administrative announcements, TA introduction.

Max Flow problem definition, Min-cost Max flow problem definition.References: None Reductions as algorithms. Single source single sink shortest path in directed graphs to Min-cost max flow problem. Max Flow to Min-cost max flow problem. What does it involve to show that the reduction is correct? References Chapter 26 CLRS. Exercises Reading Reductions as algorithms. Single source single sink shortest path in directed graphs to Min-cost max flow problem. Max Flow to Min-cost max flow problem. What does it involve to show that the reduction is correct?References: Chapter 26 CLRS. Ford Fulkerson Method, Augmenting path, Defining a residual network, Modifying the flow. Proving that the new flow is a valid flow in the original network. References Section 26.2 CLRS Exercises Reading Ford Fulkerson Method, Augmenting path, Defining a residual network, Modifying the flow. Proving that the new flow is a valid flow in the original network.References: Section 26.2 CLRS Cuts in a graph, Capacity of a cut, Flow across a cut, Max-Flow Min-Cut theorem. Proof that output of FF algorithm is a max-flow. Running time of the FF algorithm. Towards a strongly polytime algorithm. References Section 26.2 CLRS Exercises Reading Cuts in a graph, Capacity of a cut, Flow across a cut, Max-Flow Min-Cut theorem. Proof that output of FF algorithm is a max-flow. Running time of the FF algorithm. Towards a strongly polytime algorithm.References: Section 26.2 CLRS Dinitz Algorithm for Max-Flow. Definition of a layered network, Definition of a blocking flow. Overall algorithm with an example. References Exercises Reading Dinitz Algorithm for Max-Flow. Definition of a layered network, Definition of a blocking flow. Overall algorithm with an example.References: None Dinitz algorithm continued. Computing a blocking flow in the layered network. Analysis of time complexity. <br> Proof that the distance from the source to the target strictly increases across phases of the algorithm. References http://www.cse.iitm.ac.in/~meghana/CS6100/ref/Dinitz_alg.pdf Exercises Reading Dinitz algorithm continued. Computing a blocking flow in the layered network. Analysis of time complexity.

Proof that the distance from the source to the target strictly increases across phases of the algorithm.References: http://www.cse.iitm.ac.in/~meghana/CS6100/ref/Dinitz_alg.pdf Push-Relabel Algorithm. The overall intuition, invariants of the algorithm, contrast with algorithms based on augmenting paths. Illustration with an example. References CLRS. Exercises Reading Push-Relabel Algorithm. The overall intuition, invariants of the algorithm, contrast with algorithms based on augmenting paths. Illustration with an example.References: CLRS. Push Relabel continued. Height function, invariants. <br> Does the algorithm terminate? <br> Do we ever have an s-t path in the residual network<br> What is the largest height that a vertex can achieve?<br> Bound on number of relabels and number of saturating pushes. References CLRS Exercises Reading Push Relabel continued. Height function, invariants.

Does the algorithm terminate?

Do we ever have an s-t path in the residual network

What is the largest height that a vertex can achieve?

Bound on number of relabels and number of saturating pushes.References: CLRS Analysis of Push Relabel continued. Bounding the number of relabels, saturating and non-saturating pushes. Discussion on implementing push relabel. An O(n^2m) time algorithm for max-flow. <br> A small modification to the algorithm. Improving the bound on number of non-saturating pushes. An O(n^3) time algorithm for max-flow. References CLRS and see lecture notes from Prof. Roughgarden (Stanford) http://www.cse.iitm.ac.in/~meghana/CS6100/ref/Push-Relabel-Roughgarden-Stanford.pdf Exercises Reading Analysis of Push Relabel continued. Bounding the number of relabels, saturating and non-saturating pushes. Discussion on implementing push relabel. An O(n^2m) time algorithm for max-flow.

A small modification to the algorithm. Improving the bound on number of non-saturating pushes. An O(n^3) time algorithm for max-flow.References: CLRS and see lecture notes from Prof. Roughgarden (Stanford) http://www.cse.iitm.ac.in/~meghana/CS6100/ref/Push-Relabel-Roughgarden-Stanford.pdf Quick Recap of reduction from Bipartite Matching to max-flow problem. Halls Theorem and its proof via max-flow min-cut theorem. References Exercises Reading Quick Recap of reduction from Bipartite Matching to max-flow problem. Halls Theorem and its proof via max-flow min-cut theorem.References: None Cuts in Graph. Min-cut vs min-s-t cut. Finding min-cut using flow based algorithm. A simple algorithm using O(n^2) max-flow computations. Improving this algorithm to an algorithm that requires O(n) max-flow computations. References Exercises Reading Cuts in Graph. Min-cut vs min-s-t cut. Finding min-cut using flow based algorithm. A simple algorithm using O(n^2) max-flow computations. Improving this algorithm to an algorithm that requires O(n) max-flow computations.References: None Republic Day Holiday. References Exercises Reading Republic Day Holiday.References: None Min-cut in an undirected graph. Karger's randomized min-cut algorithm. Simple algorithm and its analysis to bound the error probability. References Randomized Algorithms by Motwani and Raghavan. Chapter 10. Exercises Reading Min-cut in an undirected graph. Karger's randomized min-cut algorithm. Simple algorithm and its analysis to bound the error probability.References: Randomized Algorithms by Motwani and Raghavan. Chapter 10. Fast MinCut algorithm. Start with n vertices and repeatedly contract till we reach roughly n/sqrt(2) vertices. Recurse on the graph obtained. Repeat this procedure twice. References Randomized Algorithms, Motowani Raghavan (Chapter 10) Exercises Reading Fast MinCut algorithm. Start with n vertices and repeatedly contract till we reach roughly n/sqrt(2) vertices. Recurse on the graph obtained. Repeat this procedure twice.References: Randomized Algorithms, Motowani Raghavan (Chapter 10) Analysis of Fast MinCut. Bounding the error probability. Running time of the algorithm. <br> Bound on total number of min-cuts in a graph. A simple example achieving the bound. References Chapter 10, Motwani and Raghavan. Exercises Reading Analysis of Fast MinCut. Bounding the error probability. Running time of the algorithm.

Bound on total number of min-cuts in a graph. A simple example achieving the bound.References: Chapter 10, Motwani and Raghavan. Problem Solving session. References Exercises Reading Problem Solving session.References: None **Theme 2 : Matching in graphs**- 20 meetings- Meeting 17 : Mon, Feb 06, 11:00 am-11:50 am
- Meeting 18 : Tue, Feb 07, 10:00 am-10:50 am
- Meeting 19 : Wed, Feb 08, 09:00 am-09:50 am
- Meeting 20 : Thu, Feb 09, 12:00 pm-12:50 pm
- Meeting 21 : Mon, Feb 13, 11:00 am-11:50 am
- Meeting 22 : Tue, Feb 14, 10:00 am-10:50 am
- Meeting 23 : Wed, Feb 15, 09:00 am-09:50 am
- Meeting 24 : Thu, Feb 16, 12:00 pm-12:50 pm
- Meeting 25 : Mon, Feb 20, 11:00 am-11:50 am
- Meeting 26 : Tue, Feb 21, 10:00 am-10:50 am
- Meeting 27 : Wed, Feb 22, 09:00 am-09:50 am
- Meeting 28 : Thu, Feb 23, 12:00 pm-12:50 pm
- Meeting 29 : Mon, Feb 27, 11:00 am-11:50 am
- Meeting 30 : Tue, Feb 28, 10:00 am-10:50 am
- Meeting 31 : Wed, Mar 01, 09:00 am-09:50 am
- Meeting 32 : Thu, Mar 02, 12:00 pm-12:50 pm
- Meeting 33 : Mon, Mar 06, 11:00 am-11:50 am
- Meeting 34 : Tue, Mar 07, 10:00 am-10:50 am
- Meeting 35 : Wed, Mar 08, 09:00 am-09:50 am
- Meeting 36 : Thu, Mar 09, 12:00 pm-12:50 pm

Matchings, introduction, definitions of alternating paths, augmenting paths, examples. Berge's theorem statement. References Chapter 10, Combinatorial Optimization by Papadimirtou and Steiglitz Exercises Reading Matchings, introduction, definitions of alternating paths, augmenting paths, examples. Berge's theorem statement.References: Chapter 10, Combinatorial Optimization by Papadimirtou and Steiglitz Symmetric Difference of two matchings. Using that to prove Berge's theorem. A template Algorithm for computing maximum cardinality matching in general graphs. <br> Special case of bipartite graphs. Dinic's like algorithm. References Chapter 10, Combinatorial Optimization, Papadimitriou and Steiglitz. Exercises Reading Symmetric Difference of two matchings. Using that to prove Berge's theorem. A template Algorithm for computing maximum cardinality matching in general graphs.

Special case of bipartite graphs. Dinic's like algorithm.References: Chapter 10, Combinatorial Optimization, Papadimitriou and Steiglitz. Notion of maximal vertex disjoint shortest augmenting paths. Invariants after we augment along these paths. Hopcroft Karp Algorithm with analysis of O(msqrt{n}) time. References Earlier reference as well as Chapter 3 from Introduction to Graph Theory Douglas B West. Exercises Reading Notion of maximal vertex disjoint shortest augmenting paths. Invariants after we augment along these paths. Hopcroft Karp Algorithm with analysis of O(msqrt{n}) time.References: Earlier reference as well as Chapter 3 from Introduction to Graph Theory Douglas B West. Weighted Matchings in Graphs. Formulating it as an LP. Formulating VC, Max-Flow as an LP. Dual of an LP. How to form a dual. Why is the dual useful? References Chapter on LPs in CLRS. Exercises Reading Weighted Matchings in Graphs. Formulating it as an LP. Formulating VC, Max-Flow as an LP. Dual of an LP. How to form a dual. Why is the dual useful?References: Chapter on LPs in CLRS. Primal Dual Algorithm for Max-weight matching in a bipartite graph. Equality Subgraph. Modifying the Dual. References Exercises Reading Primal Dual Algorithm for Max-weight matching in a bipartite graph. Equality Subgraph. Modifying the Dual.References: None Max-Weight Primal Dual algo continued. Definition of a labeling function. Finding a vertex cover in the equality subgraph. Which edges are having excess? How to modify Duals. References Exercises Reading Max-Weight Primal Dual algo continued. Definition of a labeling function. Finding a vertex cover in the equality subgraph. Which edges are having excess? How to modify Duals.References: None Running time analysis. O(n^4) running time algorithm. References Exercises Reading Running time analysis. O(n^4) running time algorithm.References: None Dulmage Mendelsohn Decomposition Theorem for bipartite graphs. Brief description of application to rank maximal matchings. References Exercises Reading Dulmage Mendelsohn Decomposition Theorem for bipartite graphs. Brief description of application to rank maximal matchings.References: None Non Bipartite Matchings. Edmonds algorithm. Definition of a blossom. Why is the definition useful? References Exercises Reading Non Bipartite Matchings. Edmonds algorithm. Definition of a blossom. Why is the definition useful?References: None Edmonds Blossom Shrinking Lemma with proof. How do we find blossoms? How many times do we need to "explore" a vertex to search for augmenting paths? References Exercises Reading Edmonds Blossom Shrinking Lemma with proof. How do we find blossoms? How many times do we need to "explore" a vertex to search for augmenting paths?References: None Edmonds Algorithm description. Labeling vertices odd and even. How to detect a blossom (even, even edge)? References Exercises Reading Edmonds Algorithm description. Labeling vertices odd and even. How to detect a blossom (even, even edge)?References: None Edmonds algorithm revisited. Assignment 1 solutions discussed. References Exercises Reading Edmonds algorithm revisited. Assignment 1 solutions discussed.References: None Discussion of MidSem solutions. <br> References Exercises Reading Discussion of MidSem solutions.References: None Tutte's theorem (non-biparitite equivalent of Halls theorem). Definition of a Good Set and Bad Set. Edge maximal graph. References Exercises Reading Tutte's theorem (non-biparitite equivalent of Halls theorem). Definition of a Good Set and Bad Set. Edge maximal graph.References: None Proof of Tutte's theorem continued. References Exercises Reading Proof of Tutte's theorem continued.References: None Tutte Berge Formula with its proof.<br> Deriving Hall's Theorem from Tutte's theorem. References Exercises Reading Tutte Berge Formula with its proof.

Deriving Hall's Theorem from Tutte's theorem.References: None Gallai Edmonds Decomposition theorem. References Exercises Reading Gallai Edmonds Decomposition theorem.References: None Proof of Gallai Edmond's decomposition theorem. <br> LP for Bipartite matching revisited. Proof that the extreme points of this LP are integral. The natural LP for non-bipartite matchings is not integral. References Exercises Reading Proof of Gallai Edmond's decomposition theorem.

LP for Bipartite matching revisited. Proof that the extreme points of this LP are integral. The natural LP for non-bipartite matchings is not integral.References: None Perfect Matching LP for general graphs. Proof that the LP is 1/2 integeral. <br> The odd-set constraints. After adding these constraints the LP has integral extreme points. References Exercises Reading Perfect Matching LP for general graphs. Proof that the LP is 1/2 integeral.

The odd-set constraints. After adding these constraints the LP has integral extreme points.References: None Proof of Integrality of the perfect matching polytopes in general graphs (continued from previous class). References Exercises Reading Proof of Integrality of the perfect matching polytopes in general graphs (continued from previous class).References: None **Theme 3 : Data structures and algorithms for Dynamic graphs**- 12 meetings- Meeting 37 : Mon, Apr 03, 11:00 am-11:50 am
- Meeting 38 : Tue, Apr 04, 10:00 am-10:50 am
- Meeting 39 : Wed, Apr 05, 09:00 am-09:50 am
- Meeting 40 : Thu, Apr 06, 12:00 pm-12:50 pm
- Meeting 41 : Mon, Apr 10, 11:00 am-11:50 am
- Meeting 42 : Tue, Apr 11, 10:00 am-10:50 am
- Meeting 43 : Wed, Apr 12, 09:00 am-09:50 am
- Meeting 44 : Thu, Apr 13, 12:00 pm-12:50 pm
- Meeting 45 : Mon, Apr 17, 11:00 am-11:50 am
- Meeting 46 : Tue, Apr 18, 10:00 am-10:50 am
- Meeting 47 : Wed, Apr 19, 09:00 am-09:50 am
- Meeting 48 : Thu, Apr 20, 12:00 pm-12:50 pm

To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None **Theme 4 : Matchings under preferences**- 12 meetings- Meeting 49 : Mon, Mar 13, 11:00 am-11:50 am
- Meeting 50 : Tue, Mar 14, 10:00 am-10:50 am
- Meeting 51 : Wed, Mar 15, 09:00 am-09:50 am
- Meeting 52 : Thu, Mar 16, 12:00 pm-12:50 pm
- Meeting 53 : Mon, Mar 20, 11:00 am-11:50 am
- Meeting 54 : Tue, Mar 21, 10:00 am-10:50 am
- Meeting 55 : Wed, Mar 22, 09:00 am-09:50 am
- Meeting 56 : Thu, Mar 23, 12:00 pm-12:50 pm
- Meeting 57 : Mon, Mar 27, 11:00 am-11:50 am
- Meeting 58 : Tue, Mar 28, 10:00 am-10:50 am
- Meeting 59 : Wed, Mar 29, 09:00 am-09:50 am
- Meeting 60 : Thu, Mar 30, 12:00 pm-12:50 pm

Holi Non Instructional Day. References Exercises Reading Holi Non Instructional Day.References: None Stable marriage problem. Introduction, Gale and Shapley (GS) Algorithm. Proof that GS algorithm outputs a stable matching. References Lecture notes on homepage. <br> Stable Marriage Structure and Algorithms. (by Irving and Gusfield). Exercises Reading Stable marriage problem. Introduction, Gale and Shapley (GS) Algorithm. Proof that GS algorithm outputs a stable matching.References: Lecture notes on homepage.

Stable Marriage Structure and Algorithms. (by Irving and Gusfield).Every execution of the GS algorithm outputs the same stable matching. Proof of the same.<br> Variants of the stable matchings, incomplete lists, ties. References Exercises Reading Every execution of the GS algorithm outputs the same stable matching. Proof of the same.

Variants of the stable matchings, incomplete lists, ties.References: None The case of strict and incomplete lists. Stable matchings exist. All stable matchings match the same set of vertices in A and B. Thus all stable matchings have the same size. References Exercises Reading The case of strict and incomplete lists. Stable matchings exist. All stable matchings match the same set of vertices in A and B. Thus all stable matchings have the same size.References: None Kiraly's approximation algorithm. Intuition of giving 2 chances to an unmatched participant. References Paper by Z. Kiraly (available on homepage). Exercises Reading Kiraly's approximation algorithm. Intuition of giving 2 chances to an unmatched participant.References: Paper by Z. Kiraly (available on homepage). A 3/2 approximation algo for the simple case of max. cardinality weakly stable matching with ties only on one side. References Exercises Reading A 3/2 approximation algo for the simple case of max. cardinality weakly stable matching with ties only on one side.References: None Stable matchings with ties on both sides and incomplete lists. Approximation to max. card. weakly stable matching. A 5/3 approximation algorithm. References Exercises Reading Stable matchings with ties on both sides and incomplete lists. Approximation to max. card. weakly stable matching. A 5/3 approximation algorithm.References: None Completing the proof of 5/3 approx algo for max-card. weakly stable matching. References Paper by Z. Kiraly (available on homepage). Exercises Reading Completing the proof of 5/3 approx algo for max-card. weakly stable matching.References: Paper by Z. Kiraly (available on homepage). Stable Roommates problem. References Exercises Reading Stable Roommates problem.References: None Holiday (Ugadi). References Exercises Reading Holiday (Ugadi).References: None References Exercises Reading References: None References Exercises Reading References: None