Instructors: Sanjukta Roy, Sourav Chakraborty
Lecture timing: Monday, 5th January 16:00 - 18:00
Tuesday and Wednesday 11:10 - 12:50 (starting from 7th January)
Location: room# 705
Evaluation: Your grade will be based on your performance in quizzes (20%), Midterm or class presentation (30%) , and final exam (50%).
Basic understanding of algorithms is required.
Practice problem sets for basics of Algorithms
Following are some basic books for graph theory and algorithms:
Graph Theory by Reinhard Diestel
Introduction to Graph Theory by Douglas B. West
Algorithm Design by John Kleinberg and Éva Tardos
Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
Parameterized Algorithms by Cygan et al. (2015)
Useful lecture notes: Saket Saurabh's Advance Graph Algorithm Course (2014)
Jan 5: Welcome
Jan 7: Quiz 1 . Topic: Basics of Algorithms
Feb 11: Quiz 2 . Topic: Tree decompositions: how to find them and algorithms on tree decompositions
Feb 26: Mid term
March 27: Assignment Due: Tree isomorphism
April 8: Quiz 3. Topic: Algebraic Techniques
Tree decompositions: how to find them and algorithms on tree decompositions
Algebraic techniques to solve graph problems
Graph Isomorphism
Planar graphs, Counting problems on planar graphs
Date
Topics Covered
References
05.01.2026
Lecture 1: Introduction to the course, some basics of Algorithms, NP hardness
Chapter 8 of Pre-requisit Reference 3
07.01.2026
Quiz 1: on Basics of Algorithms
13.01.2026
Lecture 2: Algorithms for finding Maximum Independent Set on Trees and its properties
Chapter 7.1 of Reference 1
Lecture 1 of Reference 2
14.01.2026
Lecture 3: t-decomposable graphs and Balanced Separators
Chapter 7.6 of Reference 1
Lecture 2 of Reference 2
20.01.2026
Lecture 4: Weighted Balanced Separators and definition of tree decomposition
Chapter 7.6 of Reference 1
Lecture 3 of Reference 2
21.01.2026
Lecture 5: Existence of tree decomposition using W-balance separators via constructive arguments
Chapter 7.6 of Reference 1
Lecture 4 of Reference 2
27.01.2026
Lecture 6: Menger's Theorem
Pre-requisit Reference 1 & 2
28.01.2026
Lecture 7: Finding approximately balanced separators, Finding Tree Decomposition, Nice tree decompositions
Lecture 5 of Reference 2
Chapter 7.6 and 7.2 of Reference 1
03.02.2026
Lecture 8: Designing algorithms using tree decompositions
Chapter 7.3 of Reference 1
04.02.2026
Lecture 9: Cops and Robber Game, Brambles. MSO2 formula, and Courcelle's Theorem
Chapter 7.4,7.5 of Reference 1
10.02.2026
Lecture 10: Graph Problems as PIT, Schwartz-Zippel lemma
Lecture 7 of Reference 2
11.02.2026
Quiz 2
18.02.2026
Lecture 11: Perfect Matching as PIT
Lecture 7 of Reference 2
26.02.2026
Mid term
04.03.2026
Lecture 12: Finding a shortest cycle using PIT
Lecture 8 of Reference 2
Section 3 & 4 from the article
Algorithmic Applications of Baur-Strassen’s Theorem: Shortest Cycles, Diameter and Matchings.
10.03.2026
Lecture 13: Planar graphs: Definitions, planar embedding, Forbidden minor characterization, 2-connected graphs
Chapter 4 of Prerequisite reference 1
Chapter 6 of Prerequisite reference 2
Chapter 7.7 of Reference 1
11.03.2026
Lecture 14: Planar graphs: Proof of Kuratowski's Theorem in 3-connected graphs, Euler's Formula, Robertson Seymour's theorem (informal)
Chapter 4 of Prerequisite reference 1
Chapter 6 of Prerequisite reference 2
Chapter 7.7 of Reference 1
17.03.2026
Lecture 15: Tree Isomorphism: Using binary certificates by Aho, Hopcroft, and Ullman
18.03.2026
Lecture 16: Graph Isomorphism: 1-dimensional Weisfeiler-Leman (1-WL) algorithm
24.03.2026
Lecture 17: Subgraph Isomorphism on bounded degree graphs: Random Separation
Chapter 5.3 of Reference 1
25.03.2026
Lecture 18: Revision on Algebraic methods, Tutte matrix and size of maximum matching
Lecture 11 of Reference 2
Matching Theory by L. Lovász and M.D. Plummer.
26.03.2026
Lecture 19: Computing perfect matching in time n^{w+1}
Lecture 11 of Reference 2
01.04.2026
Lecture 20: Paffian, determinant, and counting perfect matchings in planar graphs
Lecture 9 of Reference 2