Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Region growing for multi-route cuts   We study a number of multi-route cut problems: given a graph G=(V,E) and
connectivity thresholds k_(u,v) on pairs of nodes, the goal is to find a
minimum cost set of edges or vertices the removal of which reduces the
connectivity between every pair (u,v) to strictly below its given threshold.
These problems arise in the context of reliability in communication networks;
They are natural generalizations of traditional minimum cut problems where the
thresholds are either 1 (we want to completely separate the pair) or infinity
(we don't care about the connectivity for the pair). We provide the first
non-trivial approximations to a number of variants of the problem including for
both node-disjoint and edge-disjoint connectivity thresholds. A main
contribution of our work is an extension of the region growing technique for
approximating minimum multicuts to the multi-route setting. When the
connectivity thresholds are either 2 or infinity (the "2-route cut" case), we
obtain polylogarithmic approximations while satisfying the thresholds exactly.
For arbitrary connectivity thresholds this approach leads to bicriteria
approximations where we approximately satisfy the thresholds and approximately
minimize the cost. We present a number of different algorithms achieving
different cost-connectivity tradeoffs.

16
The categories of this paper are: stat
13
The categories of this paper are: quant-ph
23
The categories of this paper are: solv-int
33
The categories of this paper are: plasm-ph
37
The categories of this paper are: supr-con
4
The categories of this paper are: cond-mat
3
The categories of this paper are: physics
2
The categories of this paper are: math
10
The categories of this paper are: q-bio
26
The categories of this paper are: bayes-an
19
The categories of this paper are: eess
7
The categories of this paper are: hep-th
29
The categories of this paper are: funct-an
6
The categories of this paper are: astro-ph
24
The categories of this paper are: dg-ga
9
The categories of this paper are: nlin