On multiway cut parameterized above lower bounds

Authors:
Open Access
Publisher website
Google Scholar
Abstract
We introduce a concept of parameterizing a problem above the optimum solution of its natural linear programming relaxation and prove that the node multiway cut problem is fixed-parameter tractable (FPT) in this setting. As a consequence we prove that node multiway cut is FPT, when parameterized above the maximum separating cut, resolving an open problem of Razgon. Our results imply O * (4 k ) algorithms for vertex cover above maximum matching and almost 2-SAT as well as an O * (2 k ) algorithm for node multiway cut with a standard parameterization by the solution size, improving previous bounds for these problems.
Funding Information
  • Foundation For Polish Science
  • Narodowe Centrum Nauki (N206 567140)
  • European Research Council

This publication has 16 references indexed in Scilit: