menu +

Parameterized Complexity and Algorithms

An informal series of lectures in parameterized techniques
in the context of algorithm design and lower bounds.

The broad scope of these lectures will be techniques in parameterized algorithms, with some detours into parameterized reductions. Watch this space for pointers to further resources, and also advance warnings about what's in store at the next meetup :) I expect the sessions to be largely self-contained and independent of each other. Also, about ninety minutes long - give or take a few!

The first meeting will be at 2PM, October 10th, 2015 (Saturday) at Room 204, Shed 5 (note the updated timing). We tentatively expect future meetings to be held weekly, at 5PM on Fridays.

Resources. Most of the material covered will be based on chapters from Parameterized Algorithms, a book authored by Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S.

Some of the content, especially of the "tight lower bounds" flavor, is also being covered at the Fine-Grained Complexity and Algorithm Design Bootcamp, with lectures at Youtube. Specifically, the series of four lectures by Dániel Marx covers some algorithmic techniques, and subsequently W-hardness, tight lower bounds based on ETH, and tigher lower bounds based on SETH.

30 October 2015

This lecture will continue the theme of kernelization. We will show a polynomial-sized kernel for the d-Hitting Set problem, using the Sunflower Lemma. Next, we will argue a linear kernel for Vertex Cover based on its LP formulation.

Note: This session starts at 3PM.

23 October 2015

Session cancelled.

16 October 2015

This lecture will be an introduction to the notion of kernelization. We will show polynomial-sized kernels for problems like Vertex Cover, Max-SAT, Feedback Arc Set on Tournaments, and Feedback Vertex Set.

10 October 2015

We'll discuss a randomized algorithm for finding a path of length at least $k$. The goal is to do this in ${\cal O}^*(2^k)$ time and polynomial space. The approach involves formulating a polynomial that is nonzero if and only if the input graph contains a k-path. This allows us to appeal to the Schwartz-Zippel lemma to check for the existence of the path in question. If we have time, we'll compare this with other methods for finding $k$-paths, such as color coding.

Incidentally, the ${\cal O}^*$ notation is (ab)used to suppress polynomial factors, and will be used liberally on this page.

References. This discussion will be based on the last section of Chapter 10 in the book (which has a detailed bibliography with further references). There are also some slides here and here.

Please drop me a line if you have any suggestions, or leave a note in the comment forum below. I'll be sending email reminders to anyone interested, so do let me know if you are!