- Marek Cygan
- Marcin Pilipczuk
- Michał Pilipczuk
- Jakub Onufry Wojtaszczyk
IPEC 2011 (to appear)
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.
We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work