LP-Guided Branching

Guillemot [DO 2011] was the first to analyse the running time of branching algorithms in terms of excess above the value of the LP relaxation. In this last few years, this method turned out to be fruitful in parameterized complexity, and led to state-of-the-art FPT algorithms for a number of important problems, such as Almost 2-SAT or Odd Cycle Transversal. The work of Wahlström [SODA 2014] put the LP-guided branching principle in a much broader context of k-submodular CSP relaxations, significantly expanding the applicability of the method.

In the talk I will give an overview of the technique, and survey the main and the most recent results.