FPT-algorithms via LP-relaxations

Lundi 26 mars 2018, 14h, P301

Magnus Wahlström, Royal Holloway, London

LP-relaxations are traditionally (within theoretical computer science) used for computing approximate solutions to NP-hard problems, but across the last few years there have been several examples where LP-relaxations have been used to guide FPT-algorithms — that is, exact (non-approximate) algorithms whose running time is bounded in terms of a "parameter" of the input instance. This approach has given algorithms that are simultaneously simpler and faster for a range of central problems in parameterized complexity. At the same time, this is applicable only to specific problems and relaxations ; an arbitrary LP-relaxation, even one that has good properties in an approximation sense, will in general give no useful guidance with respect to exact solutions.

In this talk, we give an overview of these FPT applications, and the conditions they impose on the LP-relaxation. Our main focus is on an approach of "discrete relaxation" referred to as Valued CSPs, but we also briefly survey more immediately combinatorial conditions, as well as related algorithms that solve these problems more efficiently (e.g., so-called linear-time FPT algorithms) by bypassing the LP-solver.