Graph Partitioning with Demands: Generalized Conductance and its Applications

In this work, we study various graph partitioning problems under a general demand model. In each such task, we are given a graph G=(V,E,c,w) with a capacity function c\colon E\to \mathbb{N} and a demand function w\colon V\times V\to \mathbb{N}. Our main focus is the problem of finding a cut (S, \bar{S}) minimizing the quantity [ ψ_w( S ) = \frac{c( S, \bar{S} )}{w( S, V )\cdot w( \bar{S}, V )}. ] Here, c( S, \bar{S} ) is the cost of edges between S and the complement of S, \bar{S}, and w( S, V )=w( S )+w( S, \bar{S} ) is the sum of the internal demand within S, w( S ), and the demand between vertices of S and \bar{S}, w( S, \bar{S} ). We call ψ_w( S ) the generalized conductance of the cut (S, \bar{S}), and the task of minimizing ψ_w( S ) the Generalized Conductance Problem. Our main contribution is an algorithm with an O(\log n)-approximation guarantee for this objective. Our result is achieved via a two-way reduction: first to the well-known Generalized k-Multicut Problem, and then to a constrained variant of the classic Sparsest-Cut Problem, with an additional upper-bound constraint on the amount of demand that may be cut. Moreover, we show that the above procedure can be used to obtain an O(\log n)-bicriteria approximation for Graph Partitioning with Demands, where the goal is to find a minimum-cost subset of edges C such that for every component H of G\setminus C, w( H )\leq ρ\cdot w( V ). This, in turn, yields an O(\log n)-approximation for Hierarchical Clustering with Demands, the problem of finding a hierarchy of cuts that partitions the graph into increasingly refined clusters. For multiplicative demand functions, we improve these guarantees to O(\sqrt{\log n}) and for trees we get an O(1)-approximation for all of our objectives.