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.