Graph Partitioning with Demands: Generalized Conductance and its Applications

Abstract

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:E\to \mathbb{N}$ and a demand function $w: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 $\ddot{I}{ˆ}_w(S)$ the \emph{generalized conductance} of the cut $(S,\bar{S})$, and the task of minimizing $\ddot{I}{ˆ}_w(S)$ the Generalized Conductance Problem. Our main contribution is an algorithm with an $\mathcal{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 $\mathcal{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)\le \ddot{I}\cdot w(V)$. This, in turn, yields an $\mathcal{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 $\mathcal{O}(\sqrt{\log n})$ and for trees we get an $\mathcal{O}(1)$-approximation for all of our objectives.

24 pages

Topics & keywords