Topics in Algorithms (Jan  Apr 2013)
A Course in Parameterized Algorithms
Announcements
A list of potential papers to present from at the end of the course is available here.
Assignment 3 is now available, download here.
Assignment 2 is now available, download here.
Assignment 1 is now available, download here.
Course Timings
Mondays and Wednesdays, 1400  1530 HRS
Room 252
Schedule
Date  Topic  Notes 

07 Jan  Introduction: Pushing the Limits of Polytime Computation  
09 Jan  Color Coding: Using Colors to Discover Substructures (Applied to Longest Path)  
14 Jan  No Class  
16 Jan  Chromatic Coding: Even More Colors, Even Faster Algorithms (Applied to Clustering) Guest Lecture by Prof. Saket Saurabh. 

21 Jan  Iterative Compression: Try, try, till you succeed. Or fail. (Applied to Odd Cycle Traversal)  
23 Jan  Iterative Compression, continued.  
28 Jan  Iterative Compression and Greedy Localization: Cochromatic Number on Perfect Graphs  
30 Jan  Iterative Compression and Greedy Localization: Rectangle Stabbing  
04 Feb  Important Separators: An Introduction  
06 Feb  DFVS via Important Separators  
11 Feb  No Class  
13 Feb  Treewidth: An Introduction  
18 Feb  DP over Tree Decompositions  
18 Feb  DP over Tree Decompositions (Contd.)  
25 Feb  Preliminaries from Logic and Automata Theory 1  
27 Feb  Preliminaries from Logic and Automata Theory 2  
04 Mar  Buchi's Theorem  
06 Mar  Buchi's Theorem (Contd.)  
11 Mar  Courcelle's Theorem  
13 Mar  Courcelle's Theorem (Contd.)  
18 Mar  An Introduction to Kernelization  
20 Mar  A Cubic Kernel for Cluster Editing  
25 Mar  A Linear Kernel for Vertex Cover  
27 Mar  No Class  
1 Apr  A quadratic kernel for FVS  
3 Apr  A Quadratic Kernel for Max Leaf Spanning Tree  
8 Apr  An Introduction to Hardness of Polynomial Kernelization  
10 Apr  An Introduction to Whardness 
The Elevator Pitch
Once a problem is doomed to the fate of NPcompleteness, all evidence indicates that our chances of solving it in polynomial time are extremely slim.
Or are they?
It is true that we do not expect to solve such problems feasibly, and with complete precision, on the most general class of instances. However, we can often find loopholes that allow for solutions that are good enough in practice. Perhaps we can settle for approximate solutions, or perhaps we are only interested in solving the problem on planar graphs?
This course is a formal introduction to such loopholes. We begin where a typical first course in Algorithms ends, exploring the toolkit that has been developed to work around the NPhardness barrier. This is important because many of the 3,000+ problems that are known to be NPhard arise frequently in practice and need to be solved, and the declaration of NPhardness is not a satisfying answer.
The course will have an emphasis on parameterized algorithms and kernelization, although themes of randomization and approximation will also play an important role.
Parameterized Algorithms is a highly interdisciplinary field, and this will be emphasized in the later part of the course, where we will move on to domainspecific applications. The course content at this stage will be flexible depending on the interests of the audience, but tentatively we will look at some cornerstone applications in computational biology and artificial intelligence.
Prerequisites. A first course in the Design and Analysis of Algorithms. Familiarity with elementary graph theory is desirable, but not essential.
Topics. Fundamentals and definitions (fixedparameter tractability). Elementary techniques: bounded depth search trees, iterative compression, greedy localization, bounded variable integer linear programming, color coding, randomized divide and conquer, connections with approximation schemes. Kernelization: definitions, crown reductions, protrusion techniques, randomized kernels, matroidbased methods. Techniques based on graph structure: dynamic programming over graphs of bounded treewidth, introduction to classical tree automata and monadic secondorder logic, Courcelle’s theorem, applications of local treewidth, and other width metrics. Applications in specific areas of interest, including computational biology, geometry, and social choice theory.