Multicut is FPT

Nicolas Bousquet, Jean Daligault, Stéphan Thomassé

Let $G=(V,E)$ be a graph on $n$ vertices and $R$ be a set of pairs of vertices in $V$ called \emph{requests}. A \emph{multicut} is a subset $F$ of $E$ such that every request $xy$…