Home > Department of Mathematics > Seminars > OR Seminar Series > Academic year 2013-14 > Half-integrality, LP-branching and FPT Algorithms
How to contact us


LSE 10 logo master_6

Department of Management
London School of Economics and Political Science
Houghton Street

London WC2A 2AE


Enquiries: dom.events@lse.ac.uk 


Follow us online



Half-integrality, LP-branching and FPT Algorithms

Wednesday 22 January 2014, 5.00pm - 6.00pm
NAB 1.15, New Academic Building

Magnus Wahlström

Royal Holloway, University of London 

Personal Profile


A recent trend in parameterized algorithms is the application of polytope tools (specifically, LP-branching) to FPT algorithms (e.g., Cygan et al., 2011; Narayanaswamy et al., 2012). Though the list of work in this direction is short, the results are already interesting, yielding significant speedups for a range of important problems. However, the existing approaches require the underlying polytope to have very restrictive properties, including half-integrality and Nemhauser-Trotter-style persistence properties. To date, these properties are essentially known to hold only for two classes of polytopes, covering the cases of Vertex Cover (Nemhauser and Trotter, 1975) and Node Multiway Cut (Garg et al., 1994).

Taking a slightly different approach, we view half-integrality as a discrete relaxation of a problem, e.g., a relaxation of the search space from {0,1\}^V to {0,1/2,1}^V such that the new problem admits a polynomial-time exact solution. Using tools from CSP (in particular Thapper and Zivny, 2012) to study the existence of such relaxations, we are able to provide a much broader class of half-integral polytopes with the required properties.

Our results unify and significantly extend the previously known cases. In addition to the new insight into problems with half-integral relaxations, our results yield a range of new and improved FPT algorithms, including an O*(|Sigma|^{2k})-time algorithm for node-deletion Unique Label Cover with label set Sigma (improving the previous bound of O*(|\Sigma|^{O(k^2 \log k)}) due to Chitnis et al. (2012) and an O*(4^k)-time algorithm for Group Feedback Vertex Set, including the setting where the group is only given by oracle access (improving on the previous bound of O*(2^{O(k\log k)}) due to Cygan et al. (2012). The latter bound is optimal under the Exponential Time Hypothesis. The latter result also implies the first single-exponential time FPT algorithm for Subset Feedback Vertex Set, answering an open question of Cygan et al. (2012).

Interestingly, despite the half-integrality, our result do not imply any approximation results (as may be expected, given the Unique Games-hardness of the covered problems).



  Magnus Wahlstrom