Fast Approximation Algorithms for Cut-based Problems in Undirected Graphs
Preprint
Abstract
We present a general method of designing fast approximation algorithms for cut-based minimization problems in undirected graphs. In particular, we develop a technique that given any such problem that can be approximated quickly on trees, allows approximating it almost as quickly on general graphs while only losing a poly-logarithmic factor in the approximation guarantee. To illustrate the applicability of our paradigm, we focus our attention on the undirected sparsest cut problem with general demands and the balanced separator problem. By a simple use of our framework, we obtain poly-logarithmic approximation algorithms for these problems that run in time close to linear. The main tool behind our result is an efficient procedure that decomposes general graphs into simpler ones while approximately preserving the cut-flow structure. This decomposition is inspired by the cut-based graph decomposition of R\"acke that was developed in the context of oblivious routing schemes, as well as, by the construction of the ultrasparsifiers due to Spielman and Teng that was employed to preconditioning symmetric diagonally-dominant matrices.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Expander flows, geometric embeddings and graph partitioningJournal of the ACM, 2009
- Approximating Fractional Multicommodity Flow Independent of the Number of CommoditiesSIAM Journal on Discrete Mathematics, 2000
- Beyond the flow decomposition barrierJournal of the ACM, 1998
- An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation AlgorithmSIAM Journal on Computing, 1998
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their ApplicationsSIAM Journal on Computing, 1996
- A Graph-Theoretic Game and Its Application to the k-Server ProblemSIAM Journal on Computing, 1995
- The Complexity of Multiterminal CutsSIAM Journal on Computing, 1994
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random StartSIAM Journal on Matrix Analysis and Applications, 1992
- λ1, Isoperimetric inequalities for graphs, and superconcentratorsJournal of Combinatorial Theory, Series B, 1985
- A Theorem on Boolean MatricesJournal of the ACM, 1962