3rd to 8th March, 2014 | IMSc, Chennai


Schedule

You can find most of the slides for the talks here. Please download a PDF file of the entire schedule here. The links for the lecture notes (in draft form!) are as follows:

  1. The Basics.
  2. Intractability.
  3. Algebraic Techniques.
  4. Advanced Intractability.
  5. Treewidth and Important Separators.
  6. Advanced Kernelization.


These notes are based on a book scheduled to released later in the year, authored jointly by Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk and Saket Saurabh.

The following is a brief breakdown of the broad topics that we will cover during the school.

Part A: Algorithmic Toolkit - The Essentials

Fundamentals

Branching, Dynamic Programming over Subset Lattices, An Introduction to Kernelization: Applications of the Sunflower Lemma, Crown Reductions and Nemhausser-Trotter, Iterative Compression, Color Coding, Chromatic Coding, Graph Minors, ILP techniques, Branching in the context of above-guarantee problems, the W-hierarchy.

Treewidth

Definitions and simple examples, Courcelle's Theorem, Approximating Treewidth within a constant factor, Bidimensionality, Cops and Robbers formulation, Irrelevant Vertices.

Important separators

Definition, The 4^k bound, Shadow removal, Treewidth Reduction with Applications.

Algebraic techniques

Transforms (Mobius, Zeta, Subset Convolution), Inclusion-Exclusion (with examples), Determinant based r-Dimensional Matching Algorithm, Isolation Lemma, Cut and Count for Steiner Tree, Rank-based approach for Steiner Tree.

Part B: More Kernelization and Lower Bounds

Kernelization Revisited

Quadratic Kernel for FVS, Kernels on Planar Graphs using Region Decompositions, Cluster Editing and Modules, Kernels for Above Guarantee Problems.

Matroids

Matroids: Basics and Definitions, Gammoid Representation Theorem, Representative Sets, Cut Covering Lemma, Kernel for OCT, Dynamic Programming over Graphs of Bounded Treewidth, Finding k-vertex cycles in single-exponential time.

Kernelization
Lower Bounds

OR-compositions, Cross Compositions, Reductions, Weak Compositions.

Complexity
Lower Bounds

An Introduction to the W-hierarchy, The Exponential Time Hypothesis, The Sparsification Lemma, The Strong Exponential Time Hypothesis, Various Examples of Reductions.