An $O^{\ast }(1.84^k)$ Parameterized Algorithm for the Multiterminal Cut Problem

Yixin Cao, Jianer Chen, Jia-Hao Fan

We study the \emph{multiterminal cut} problem, which, given an $n$-vertex graph whose edges are integer-weighted and a set of terminals, asks for a partition of the vertex set such…