On Multiway Cut paramterized above lower bounds

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.