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

Abstract

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 and the goal is to delete a minimum-cost set of edges to reduce the edge-connectivity of every source-sink pair to below $k$. The $k$-route extensions of multiway cut ($k$-MWC), and the minimum $s$-$t$ cut problem ($k$-$(s,t)$-cut), are similarly defined. We present various approximation and hardness results for these $k$-route cut problems that improve the state-of-the-art for these problems in several cases. (i) For {\em $k$-route multiway cut}, we devise simple, but surprisingly effective, combinatorial algorithms that yield bicriteria approximation guarantees that markedly improve upon the previous-best guarantees. (ii) For {\em $k$-route multicut}, we design algorithms that improve upon the previous-best approximation factors by roughly an $O(\sqrt{\log r})$-factor, when $k=2$, and for general $k$ and unit costs and any fixed violation of the connectivity threshold $k$. The main technical innovation is the definition of a new, powerful \emph{region growing} lemma that allows us to perform region-growing in a recursive fashion even though the LP solution yields a {\em different metric} for each source-sink pair. (iii) We complement these results by showing that the {\em $k$-route $s$-$t$ cut} problem is at least as hard to approximate as the {\em densest-$k$-subgraph} (DkS) problem on uniform hypergraphs.