Graph Partitioning with Demands: Generalized Conductance and its Applications

We study various graph partitioning tasks subject to general demands. In Graph Partitioning with Demands (GPD), the goal is to delete minimum cost supply edge set so that each remaining component contains at most a prescribed fraction of the total demand. In the hierarchical analogue of this problem, Hierarchical Clustering with Demands (HCD), the goal is to build a hierarchy of clusters, charging each supply edge by the demand in the smallest cluster containing its endpoints. Our main general-graph results are approximation algorithms for GPD and HCD. For every fixed 0<ρ<η<1, we give a polynomial-time bi-criteria algorithm for GPD whose components have demand at most η times W and cost at most O ρ,η(sqrt n) times the optimum cost for threshold ρ. This procedure can then be applied recursively to obtain an O(sqrt n) -approximation for HCD. The algorithm for GPD itself uses a crucial subproblem called Generalized Conductance (GC), a new generalization of the Sparsest Cut. On supply trees, we show that GC can be solved exactly in polynomial time. We also give bi-criteria algorithms for GPD based on anchored-LP rounding and separator recursion, as well as a single-criterion (4+ε) -approximation in n O(1/ρ) time. Moreover, through previous reduction, these GPD algorithms yield a 4e over e-1-approximation for HCD on trees. We also prove that HCD and GPD and GC are SSEH-hard to approximate within any constant factor. On trees, assuming the Unique Games Conjecture (UGC), GPD is hard to approximate within a factor of 2-ε by reduction from Vertex Cover, while HCD is hard to approximate within a factor of 1.0748, by reduction from Min-Sum Vertex Cover.