Improved region-growing and combinatorial algorithms for κ-route cut problems

We study the k-route generalizations of various cut problems, the most general of which is 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 κ-route extensions of multiway cut (fc-MWC), and the minimum s-t cut problem (k-(s,t)-Cut), are similarly defined. We present various approximation and hardness results for k-MC, κ-MWC, and k-(s,t)-Cut that improve the state-of-the-art for these problems in several cases. Our contributions are threefold. For 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. For k-route multicut, we design algorithms that improve upon the previous-best approximation factors by roughly an (9(√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 region growing lemma that allows us to perform region-growing in a recursive fashion even though the LP solution yields a different metric for each source-sink pair, and without incurring an O(log²r) blow-up in the cost that is inherent in some previous applications of region growing to κ-route cuts. We obtain the same benefits as [15] do in their divide-and-conquer algorithms, and thereby obtain an 0(lnrlnlnr)-approximation to the cost. We also obtain some extensions to k-route node-multicut problems. We complement these results by showing that the k-route s-t cut problem is at least as hard to approximate as the densest-k-subgraph (DkS) problem on uniform hypergraphs. In particular, this implies that one cannot avoid a poly(κ)-factor if one seeks a unicriterion approximation, without improving the state-of-the-art for DfcS on graphs, and proving the existence of a family of one-way functions. Previously, only iVP-hardness of k-(s,t)-Cut was known.