Campus Event Calendar

Event Entry

What and Who

Faster FPT algorithms using Linear Programming

Saket Saurabh
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience

Date, Time and Location

Tuesday, 28 February 2012
30 Minutes
E1 4


We investigate the parameterized complexity of Vertex Cover parameterized above the optimum value of the linear programming (LP) relaxation of the integer linear programming formulation of the problem. We first consider the straightforward branching algorithm for

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.


Danny Hermelin
--email hidden
passcode not visible
logged in users only

Danny Hermelin, 02/24/2012 14:06 -- Created document.