Recent Topics in Parameterized Complexity

This is a three-part lecture taught by Cornelius Brand, Andreas Emil Feldmann and myself.

Topics will be roughly:

1. Parameterized algorithms for integer programming and their applications in scheduling. (Martin)
2. Hard graph problems (e.g., longest path, longest cycle) via algebraic methods; this will be an elementary exposition, so everyone is welcome. (Cornelius)
3. Parameterized approximation (i.e., how to deal with problems which are hard to approximate and do not admit fixed-parameter algorithms), in particular for network design. (Andreas)

First lecture: we talked about Integer Linear Programming with few constraints and without upper bounds, that is, the problem is $\min \mathbf{c} \mathbf{x}: \, A \mathbf{x} = \mathbf{b}, \, \mathbf{x} \geq \mathbf{0}, \, \mathbf{x} \in \mathbb{Z}^n$. First we mentioned an old algorithm of Papadimitriou with a dependence of roughly $(m \Delta)^{O(m^3)}$, where $m$ is the number of rows and $\Delta$ is the largest coefficient of $A$ in absolute value. Then, we studied a new algorithm of Eisenbrand and Weismantel (arxiv) which improves the runtime to roughly $(m \Delta)^{O(m)}$; also see an algorithm of Jansen and Rohwedder which improves the constants in the exponent. Finally, we talked about using this algorithm to get an algorithm for the scheduling problem $P||C_{\max}$ which runs in time roughly $p_{\max}^{O(p_{\max})}$ instead of the $p_{\max}^{O(p_{\max}^2)}$ time implied by Knop and Koutecký (arxiv).

Second & Third lecture: We talked about Huge $n$-fold Integer Programming, solving its Configuration LP and that a solution derived from it satisfies stronger proximity bounds than the solution of a normal relaxation. This is based on MIMO, Section 3. I did not go into the full detail and you are not required to understand all of the proofs, but please try to understand the main concepts and statements, which are:

• Definition of the Huge $n$-fold IP problem
• The Configuration LP of the Huge $n$-fold IP (equations (3)-(4))
• How the Configuration LP is solved in FPT time by solving its Dual by the Ellipsoid method (separation oracle) (Lemma 12)
• The definition of a configurable cycle (pg. 14) and some of its properties: Lemmas 13-15
• The proximity theorem (Thm 21) and how it is used to obtain an FPT algorithm for Huge $n$-fold IP (Proof of Thm 5)

It would be also great if you had an idea of how the proximity theorem is used to obtain kernels for scheduling problems.

Fourth lecture: We talked about Mixed Integer Linear Programs, notes are here. In particular note we discussed a neat trick of Hochbaum-Shantikumar on how to get a Separable Convex IP algorithm from a Linear IP algorithm.

Covered topics and references:

1. Lossy kernels: sections 1 and 2 of Lokshanov et al.
2. PSAKS for Steiner Tree parameterized by nr of terminals: section 6.2 of Lokshanov et al.
3. Proof of Borchers and Du Theorem: sections 1 and 3 of Borchers and Du
4. Directed Steiner Tree parameterized by nr of Steiner vertices: sections 1, 4, and 5 of Dovřak et al.
5. Undirected Steiner Tree (and Steiner Forest) parameterized by nr of Steiner vertices (and nr of connected components): sections 1 and 3 of Dvořak et al.