On Multiway Cut paramterized above lower bounds
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.