menu +

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: 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.