On Multiway Cut paramterized above lower bounds

Marek Cygan
Marcin Pilipczuk
Michał Pilipczuk
IPEC 2011 (to appear)

Abstract

In this paper we consider two above lower bound parameterizations of Node Multiway Cut — above maximum separating cut and above a natural LP-relaxation — and prove them to be fixed-parameter tractable. Our results imply O(4^k) algorithms for Vertex Cover above Maximum Matching and Almost 2-SAT as well as a O*(2^k) algorithm for Node Multiway Cut with a standard parameterization by the solution size, improving previous bounds for these
problems.