TITLE: LP-relaxations for FPT algorithms
SPEAKER: Magnus Wahlstrom (Royal Holloway)

ABSTRACT:

We consider applications of polytope methods (e.g., LP-relaxations) to
FPT algorithms.

An FPT algorithm is an algorithm with a running time of f(k)*poly(n) for
some function f(k), where k is the value of a parameter of the input
(e.g., for an optimisation problem, k could be a bound on the solution
size). This leads to tractable algorithms for many NP-hard problems for
cases where the parameter is small (although the instance itself may be
large).

Traditionally, FPT algorithms have been explicitly combinatorial, however,
for a few problems the best FPT algorithm known is based on a suitable
LP-relaxation of the problem. This has the potential to yield powerful
results, however, with the tools known so far, the approach requires some
very specific properties of the LP-relaxation (half-integrality and
persistence), properties which only a few LPs are known to have.

In this talk, we show a broader class of LP-relaxations meeting these
criteria, encompassing and extending all previous cases. The result is a
broader class of half-integral relaxations, and significantly improved FPT
algorithms for a range of problems, including the first 2^O(k)-time
algorithms for the Subset Feedback Vertex Set and Group Feedback Vertex
Set problems (described in the talk).

This talk is based on results from SODA 2014.