Improved Region-Growing and Combinatorial Algorithms for $k$-Route Cut Problems

Guru Guruganesh, Laura Sanita, Chaitanya Swamy

We study the {\em $k$-route} generalizations of various cut problems, the most general of which is \emph{$k$-route multicut} ($k$-MC) problem, wherein we have $r$ source-sink pairs…