Improved Region-Growing and Combinatorial Algorithms for k-Route Cut Problems
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(logr)-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.
