HALF-INTEGRALITY, LP-BRANCHING, AND FPT ALGORITHMS

作者：Iwata Yoichi^*; Wahlstrom Magnus; Yoshida Yuichi

来源：SIAM Journal on Computing, 2016, 45(4): 1377-1411.

DOI：10.1137/140962838

• fixed parameter tractability
• k-submodularity

A recent trend in parameterized algorithms is the application of polytope tools to fixed-parameter tractable (FPT) algorithms [e.g., Cygan et al., FOCS 2011, 52nd Annual Symposium on Foundations of Computer Science, IEEE, 2011, pp. 150-159; Narayanaswamy et al., STACS 2012, Symposium on Theoretical Aspects of Computer Science, 2012, pp. 338-349]. Although this approach has yielded significant speedups for a range of important problems, it requires 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, Math. Program., 8 (1975), pp. 232-248] and NODE MULTIWAY CUT [Garg et al., J. Alg., 50 (2004), pp. 49-61]. 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 constraint satisfaction problems [in particular Thapper and Zivny, FOCS 2012, 53rd Annual Symposium on Foundations of Computer Science, IEEE, 2012, pp. 669-678] 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, and yield a range of new and improved FPT algorithms, including an 0* (|Sigma|(2k))-time algorithm for node-deletion UNIQUE LABEL COVER and an 0* (4(k))-time algorithm for GROUP FEEDBACK VERTEX SET where the group is given by oracle access. 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. [Algorithmica, 74 (2016), pp. 630-642]. Additionally, we propose a network-flow-based approach to solve several cases of the relaxation problem. This gives the first linear-time FPT algorithm to edge-deletion UNIQUE LABEL COVER.

• 出版日期2016