Advertisement
Published in:
2012 | OriginalPaper | Chapter
On Multiway Cut Parameterized above Lower Bounds
Authors : Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk
Published in: Parameterized and Exact Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper we consider two
above lower bound
parameterizations of the
Node
Multiway Cut
problem — above the 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 an
O
*
(2
k
) algorithm for
Node
Multiway Cut
with a standard parameterization by the solution size, improving previous bounds for these problems.