On the Dominant of the Multicut Polytope

Markus Chimani, Martina Juhnke-Kubitzke, Alexander Nover

Given a graph $G=(V,E)$ and a set $S\subseteq \left(\genfrac{}{}{0ex}{}{V}{2}\right)$ of terminal pairs, the minimum multicut problem asks for a minimum edge set $\delta \subseteq E$ such that there is no $s$-$t…