Topics in Algorithms (Jan - Apr 2013)
A Course in Parameterized Algorithms
A list of potential papers to present from at the end of the course is available here.
Mondays and Wednesdays, 1400 - 1530 HRS
|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|
|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 W-hardness|
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.