Faster FPT algorithms using Linear Programming

vertex cover and by analyzing the change in the LP value in the branching steps, we argue that this algorithm itself runs in time O(2.6181^r n^{O(1)}) where r is the excess of the vertex cover size over the LP optimum. Following this, we introduce new branching rules which exploit additional structure in the instance, resulting in an algorithm running in time O(2.3146^r n^{O(1)}). We then show how this algorithm speeds up algorithms for several other parameterized problems including Odd Cycle Transversal (OCT). This is the first major improvement for OCT after the first algorithm (whose runtime was $O^*(3^k)$) that showed it to be fixed-parameter tractable in 2003.