(Multiterminal) cut problems
[1]}, [2]}, [3]}, [4]}
play a mysterious,
and not yet fully understood, role in the fixed-parameter tractability of
certain problems. Proving that bipartization
[5]}, directed feedback vertex set
[6]}, and almost 2-sat
[7]} are fpt answered longstanding open questions,
and in each case the algorithm relies on a non-obvious use of
separators. Furthermore, edge multicut has been observed to
be equivalent to fuzzy cluster editing, a correlation
clustering problem
[8]}, [9]}, [10]}.
Thus aiming for a better understanding of separators in a
parameterized setting seems to be a fruitful direction of research.
Our results extend our understanding of separators by showing that
various additional constraints can be accommodated. It is important to
point out that our algorithm is very different from previous
parameterized algorithms for separation problems
[1]}, [2]}, [3]}, [4]}.
Those algorithms in the literature exploit certain nice properties
of separators, and hence it seems impossible to generalize them for
the problems we consider here. On the other hand, our approach is very
robust and, as demonstrated by our examples, it is able to handle many
variants.
