2019-07-31 Magnus Wahlström, FPT algorithms via LP relaxations

IBS Discrete Mathematics Group
IBS Summer Research Program on Algorithms and Complexity in Discrete Structures
Magnus Wahlström, FPT-algorithms via LP-relaxations
July 31 2019, Wednesday @ 10:00 AM ~ 11:00 AM
Room B232, IBS (기초과학연구원)
Speaker
Magnus Wahlström
Royal Holloway, University of London, UK
pure.royalholloway.ac.uk/port...
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.