### Obsah

# Recent Topics in Parameterized Complexity

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

Topics will be roughly:

- Parameterized algorithms for integer programming and their applications in scheduling.
*(Martin)* - Hard graph problems (e.g., longest path, longest cycle) via algebraic methods; this will be an elementary exposition, so everyone is welcome.
*(Cornelius)* - 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)*

## Parameterized algorithms for IP and applications

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

## Parameterized Approximations for Steiner Trees

Covered topics and references:

- Lossy kernels: sections 1 and 2 of Lokshanov et al.
- PSAKS for Steiner Tree parameterized by nr of terminals: section 6.2 of Lokshanov et al.
- Proof of Borchers and Du Theorem: sections 1 and 3 of Borchers and Du
- Directed Steiner Tree parameterized by nr of Steiner vertices: sections 1, 4, and 5 of Dovřak et al.
- 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.