Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset

Rajesh Chitnis, MohammadTaghi Hajiaghayi, Dániel Marx

Given a directed graph $G$, a set of $k$ terminals and an integer $p$, the \textsc{Directed Vertex Multiway Cut} problem asks if there is a set $S$ of at most $p$ (nonterminal) ver…