COL751 / COL7151: Algorithmic Graph Theory

Evaluation: The course policy is:

• Exams:  35% + 35%
• Quizzes (best n-1 out of n):  15%
• Research Project:  10%
• Class participation and attendance:  5%

Passing criteria: 30% in course total

Audit-pass criteria: 45% in course total and at least 75% attendance

Acadmic Honesty: Cheating or allowing anyone to copy would lead to a penalty of one grade per assignment / quiz / exam.

Here is a tentative list of topics that will be covered in the course:

• Aysmptotic Complexity, Hitting Set
• Distance Oracles, All-Pairs approximate distance computation
• Min-sum products, computing shortest paths via Min-sum products, Seidel's algorithm, and shortest path reconstruction
• Algebraic algorithms for shortest paths
• Algorithm for computing max-flow
• Recap of Ford-Fulkerson algorithm, Edmond-Karp's algorithm, Capacity Scaling algorithm, Min-cost flows and applications
• Submodularity of Cuts, Structural properties of min-cuts
• Karger-Stein's near-quadratic time algorithm for Global min-cuts
• k-edge Connectivity Preserver
• Gomory-Hu tree computation
• Prim's/Kruskal's/Borvka's algorithms, Karger-Klein-Tarjan linear-time randomized algorithm for MSTs
• Edmonds algorithm for arborescences (aka directed MSTs)
• Maximum matching in bipartite and general graphs
• Hall’s theorem, Tutte’s theorem, Gallai-Edmonds decomposition
• Algebraic algorithms for perfect matching
• Properties of Planar graphs, Kuratowski’s theorem, Algorithms for checking planarity, Planar-separator theorem and its applications