Teaching Group:
Instructor: Dr. Pallavi Jain
Assistant Professor
IIT Jodhpur
Course objective:
If you have ever
used google maps or any navigation system to find the shortet route, then you have used graph algorithms (Shortest Path)
played Sudoku, then you have used graph algorithms (Graph Coloring)
Many real-world situations can be formulated as graphs, e.g., road networks, computer networks, social networks, web graph, airline scheduling, etc. In this course, you will learn several efficient algorithms for graph-theoretic problems.
Prerequisites:
Maths for Computing/Discrete Mathematics
Algorithms
Class Schedule:
Monday, Wednesday, Thursday : 10:00 - 10:50 AM
Location: CS333
Attendance Requirements: as per institute policy.
Office Hours:
If you want to discuss with instructor, then schedule an appointment through email.
Grading Policy:
The following grading policy is tentative. It might change depending on the class size.
Major Exam : 40%
Minor Exams: 20%
Class Participation: 5%
Assignments: 20% (The evaluation will be based on oral presentation. You will be called randomly to discuss the solution in the class.)
Group Project: 15% (You will be expected to read a paper and present in the class. The mode of the presentation can be decided by the students, i.e., it can be either slides or board presentation. Group size = 2)
Lectures:
Some of the lecture videos can be found here.
Lecture 1: Introduction to the course, Basic graph definitions, Algorithm to find a u-v walk of length at most k in the graph.
Lecture 2: Algorithm to find a u-v walk of length at least/exactly k in the graph. Counting the number of u-v walks of length k in the graph. Counting triangles.
Lecture 3: Efficient algorithm for counting the number of u-v walks of length k in the graph, Counting triangles, Algorithm for integer multiplication, Algorithm for matrix multiplication. [Integer Multiplication in O(n log n) time]
Lecture 4+5: Algorithm for All Pair Shortest Distance. [Reference]
Lecture 6: Algorithm for All Pair Shortest Path. [Reference]
Lecture 7: Assignment 1
Lecture 8: Maximum Matching in Bipartitie Graphs: O(nm) algorithm
Lecture 9+10: Maximum Matching in Bipartitie Graphs: Hopcroft-Karp algorithm [Reference]
Extra Class on January 26, 2024 at 9:00 AM
Lecture 11: Maximum Weight Matching in Bipartite Graphs
Lecture 12+13: Edmonds' Blossom Algorithm for Maximum Sized Matching in General Graphs
Lecture 14: Assignment 2
Lecture 15: Algorithm for Vertex Cover in Bipartite Graphs, NP-hardness of Vertex Cover in General Graphs
Lecture 16: Approximation algorithm for Vertex Cover
Lecture 17: Approximation algorithm for Vertex Cover
Lecture 18 +19: Linear Programming: Tool to design (1) polynomial time exact algorithm for Vertex Cover in Bipartite graph and (2) approximation algorithm for Vertex Cover in general graphs
Mid-term project presentation on 4th March
Lecture 20: Assignment 3
Lecture 21: Exact Exponential Time Algorithm for Vertex Cover
Lecture 22: Parameterized Algorithm for Vertex Cover
Lecture 23: Parameterized approximation algorithm for Vertex Cover
Lecture 24: Network Flows [Chapter 7 in KT, Chapter 10&11 in JE]
Lecture 25: Network Flows [Chapter 7 in KT, Chapter 10&11 in JE]
Lecture 26: Network Flows [Chapter 7 in KT, Chapter 10&11 in JE]
Lecture 27: Network Flows [Chapter 7 in KT, Chapter 10&11 in JE]
Lecture 28: Network Flows [Chapter 7 in KT, Chapter 10&11 in JE]
Lecture 29: Network Flows [Chapter 7 in KT, Chapter 10&11 in JE]
Lecture 30: Network Flows [Chapter 7 in KT, Chapter 10&11 in JE]
Lecture 31: Assignment 4
Lecture 32: Treewidth [Chapter 10 in KT, Chapter 7 in CFKLMPPS]
Lecture 33: Algorithm for Maximum Weight Independent Set in Trees [Chapter 10 in KT, Chapter 7 in CFKLMPPS]
Lecture 34: Algorithm for Maximum Weight Independent Set in Bounded Treewidth Graphs: 4^{tw}.(n+tw)^{O(1)}and 2^{tw}.(n+tw)^{O(1)}[Chapter 10 in KT, Chapter 7 in CFKLMPPS]
Lecture 35: Nice Tree Decomposition
Lecture 36: Approximation Algorithm for Treewidth [Chapter 7 in CFKLMPPS]
Lecture 37: Approximation Algorithm for Treewidth-- continued [Chapter 7 in CFKLMPPS]
Lecture 38: Approximation Algorithm for Treewidth-- continued [Chapter 7 in CFKLMPPS]
Lecture 39: Assignment 5
Lectures 40 (22nd April): Project Presentation: School Redistricting: Wiping Unfairness Off the Map by Gaurv and Neielotpal
Lectures 41 (24th April): Project Presentation: Graph Search Trees and their leaves by Ashutosh and Ujjwal
Lecture 42 (25th April): Project Presentation: Practical Graph Isomorphism by Devang and Hemant
Project Suggestions:
Complexity results for matching cut problems in graphs without long induced paths [WG 2023]
Graph Search Trees and Their Leaves [WG 2023]
Critical Relaxed Stable Matchings with Two-Sided Ties [WG 2023]
Fast 2-Approximate All-Pairs Shortest Paths [SODA 2024]
School Redistricting: Wiping Unfairness Off the Map [SODA 2024]
Santa Claus meets Makespan and Matroids: Algorithms and Reductions [SODA 2024]
A Faster Combinatorial Algorithm for Maximum Bipartite Matching [SODA 2024]
Odd Cycle Transversal on $P_5$-free Graphs in Quasi-polynomial Time [SODA 2024]
A Scaling Algorithm for Weighted f-Factors in General Graphs [ICALP 2020]