FPT algorithms via biased graphs

FPT algorithms (fixed-parameter tractable algorithms) are a method of dealing with NP-hard problems that has been growing in traction across the last few decades. The basic idea is that even though a problem may be NP-hard in full generality, we may still encounter instances of this problem that are for some identifiable reason easier to deal with than the hypothetical worst-case instances. The most classical example is Vertex Cover: to the best of our knowledge, this problem requires exponential time in the worst case, but if we have a bound k (k << n) on the solution size, then the problem can be solved in time O(m + n*2^k).

For an important and growing class of problems, the fastest known FPT algorithms are based on underlying LP-relaxations – essentially branch-and-bound algorithms with an FPT performance guarantee.

However, these algorithms require the underlying LP to have some very restrictive properties (persistence and half-integrality), which limits the applicability of the approach. The best known results so far uses an algebraic connection to Valued CSP problems; however, the applicability of this algebraic approach for a given combinatorial problem is again non-trivial to check.

In this talk, we present an alternative way of producing such results, by phrasing problems as cycle-hitting problems in combinatorially defined objects called biased graphs, known from their applications in matroid theory. This gives a surprisingly flexible and versatile problem setting, which covers and extends several of the previously known cases of FPT LP-branching algorithms.