Graphs are ubiquitous mathematical objects used to model several fundamental combinatorial questions and algorithms. Algorithms form the core of computing. This course will cover several classical and modern topics in graph algorithms. The emphasis will be on developing problem solving skills. We will also cover topics that exhibit limitations on designing efficient algorithms (NP-completeness) and ways to cope with such limitations (including approximation algorithms and parameterized complexity).


Names and affiliation of speakers and course associates.

1. Aritra Banik, NISER Bhubaneswar
2. L. Sunil Chandran, IISc Bangalore
3. K. Murali Krishnan, NIT Calicut
4. Venkatesh Raman, IMSc Chennai
5. N. S. Narayanaswamy, IIT Madras
6. Jasine Babu, IIT Palakkad

Syllabus to be covered in terms of modules:
Module-1:

•  Basic Graph theory and Graph Algorithms (BGA: 3 lectures)
• Degree sequence, Havel Hakimi theorem etc
• Graph representations, BFS and applications
• DFS and applications
• Algorithms on Weighted Graphs (Shortest Paths, Minimum Spanning Trees) including correctness proofs and implementation details using data structures. (3 lectures)

Module-2:

•  Geometric Algorithms (GA: 3 lectures): Convex Hull, Voronoi Diagram, Algorithm for Closest point in 2D
• Network Flows (NF: 3 lectures): Max-Flow Min Cut theorem, Ford-Fulkerson Algorithms, Applications and faster algorithms

Module-3:

• NP-completeness definitions and reductions through examples (2 lectures)
• Clique, Vertex Cover, TSP, Set Cover, number problems like partition, knapsack (3 lectures)

Module-4:

• Approximation algorithms for vertex cover, steiner tree, triangle TSP, maxcut, maxsat, knapsack, set cover including various types of approximation algorithms like PTAS, FPTAS and linear program based techniques. (7 lectures)

Module 5:

• Parameterized Algorithms (PC: 5 lectures)
• Algorithms using branching, kernelization, iterative compression
• Treewidth and related concepts and algorithms using them.
• parameterized hardness

Module 6:

• Algorithms on special graph classes including in chordal, interval, comparability and perfect graphs
• Boxicity and related concepts . (5 lectures)

Names of speakers:

1. Prof N.S.Narayanaswamy (NSN), IIT Madras
2. Dr Aritra Banik (AB), NISER Bhubaneshwar
3. Prof Venkatesh Raman (VR), IMSc Chennai
4. Prof K Muralikrishnan (Murali), NIT Calicut
5. Dr Jasine Babu (Jasine), IIT Palakkad
6. Prof Sunil Chandran (Sunil), IISc Bangalore

Names of Course associates:

1. Ms. Rani M R (Rani), NIT Calicut
2. Ms. Remi Raman (Remi), NIT Calicut
3. Ms. Neeta Eapen (Neeta), NIT Calicut
4. Ms. Dhanyamol Antony (Dhanya), NIT Calicut
5. Ms. Rema M (Rema), NIT Calicut