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.  
Due Date: May 1, 2013. Send me an email if you have any questions about the assignment problems. 
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: Co-chromatic 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	PDF
11 Feb	No Class
13 Feb	Treewidth: An Introduction	PDF
18 Feb	DP over Tree Decompositions	PDF
18 Feb	DP over Tree Decompositions (Contd.)
25 Feb	Preliminaries from Logic and Automata Theory 1	PDF
27 Feb	Preliminaries from Logic and Automata Theory 2	PDF
04 Mar	Buchi's Theorem	PDF
06 Mar	Buchi's Theorem (Contd.)	PDF
11 Mar	Courcelle's Theorem	PDF
13 Mar	Courcelle's Theorem (Contd.)	PDF
18 Mar	An Introduction to Kernelization	PDF
20 Mar	A Cubic Kernel for Cluster Editing	PDF
25 Mar	A Linear Kernel for Vertex Cover	PDF
27 Mar	No Class
1 Apr	A quadratic kernel for FVS	PDF
3 Apr	A Quadratic Kernel for Max Leaf Spanning Tree	PDF
8 Apr	An Introduction to Hardness of Polynomial Kernelization	PDF
10 Apr	An Introduction to W-hardness	PDF

The Elevator Pitch

Once a problem is doomed to the fate of NP-completeness, 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 NP-hardness barrier. This is important because many of the 3,000+ problems that are known to be NP-hard arise frequently in practice and need to be solved, and the declaration of NP-hardness 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 domain-specific 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.

Pre-requisites. A first course in the Design and Analysis of Algorithms. Familiarity with elementary graph theory is desirable, but not essential. 

Topics. Fundamentals and definitions (fixed-parameter 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, matroid-based methods. Techniques based on graph structure: dynamic programming over graphs of bounded treewidth, introduction to classical tree automata and monadic second-order 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.