Google Research

On Multiway Cut paramterized above lower bounds

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.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work