COL751: Algorithmic Graph Theory

Evaluation: The tentative course evaluation policy is:

• Assignments:  3 x 10 = 30%
• Exams:  25% + 30%
• Quizzes (best 2 out of 3):  10%
• Attendance:  5%
• Research Project (extra weightage):  20%

Passing criteria: 30% in course total

Audit-pass criteria: 45% in course total

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 Preservers, Distance Oracles
• All-Pairs approximate distance computation
• Algorithm for computing max-flow
• Max-flow Min-cut theorem
• Structural properties of min-cuts
• k-edge Connectivity Preserver
• Gomory-Hu tree computation
• All-Pairs Bounded-min-cut algorithm
• Maximum matching in bipartite and general graphs
• Hall’s theorem, Tutte’s theorem, Gallai-Edmonds decomposition
• Arborescences and Branchings, Edmonds theorem for disjoint arborescences
• Streaming algorithms