Advertisement
Published in:
2015 | OriginalPaper | Chapter
Finding cuts and separators
Authors : Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
Published in: Parameterized Algorithms
Publisher: Springer International Publishing
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
The notion of important cuts and the related combinatorial bounds give a useful tool for showing the fixed-parameter tractability of problems where a graph has to be cut into certain parts. We discuss how this technique can be used to show that
E
dge
M
ultiway
C
ut
and
D
irected
F
eedback
V
ertex
S
et
are FPT. Random sampling of important separators is a recent extension of this method, making it applicable to a wider range of problems. We illustrate how this extension works on a clustering problem called (p, q)-
P
artition
.