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 ccolon E→ mathbbN and a demand function wcolon V× V→ mathbbN. Our main focus is the problem of finding a cut (S, barS) minimizing the quantity [ psiw( S ) = fracc( S, barS )w( S, V )· w( barS, V ). ] Here, c( S, barS ) is the cost of edges between S and the complement of S, barS, and w( S, V )=w( S )+w( S, barS ) is the sum of the internal demand within S, w( S ), and the demand between vertices of S and barS, w( S, barS ). We call psiw( S ) the generalized conductance of the cut (S, barS), and the task of minimizing psiw( 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 Gsetminus C, w( H )≤ ρ· 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(√log n) and for trees we get an O(1)-approximation for all of our objectives.