Simple and Fast Rounding Algorithms for Directed and Node-weighted Multiway Cut

Chandra Chekuri, Vivek Madan

In Directed Multiway Cut(Dir-MC) the input is an edge-weighted directed graph $G=(V,E)$ and a set of $k$ terminal nodes $\{s_1,s_2,\dots ,s_k\}\subseteq V$; the goal is to find a…