Algorithms for 2-Route Cut Problems
Chandra Chekuri, UIUC
December 7, 2007, 3:30PM, Wean 7220
Abstract:
We study approximation algorithms for multi-route cut problems in undirected graphs. In these problems the goal is to find a minimum cost set of edges to be removed from a given graph such that the edge-connectivity (or node-connectivity) between certain pairs of nodes is reduced below a given threshold $K$. In the usual cut problems the edge connectivity is required to be reduced below $1$ (i.e. disconnected).
We consider the case of $K=2$ and obtain poly-logarithmic approximation algorithms for fundamental cut problems including single-source, multiway-cut, multicut, and sparsest cut. These cut problems are dual to multi-route flows that are of interest in fault-tolerant networks flows. Our results show that the flow-cut gap between $2$-route cuts and $2$-route flows is poly-logarithmic in undirected graphs with arbitrary capacities. $2$-route cuts are also closely related to well-studied feedback problems and we obtain algorithms for some new variants.
Our algorithms are based on a new randomized scaling procedure combined with known algorithms for standard (1-route) cut problems. Several open problems will be discussed.
Joint work with Sanjeev Khanna (U. Penn)
