Graph Partitioning with Demands: Generalized Conductance and its Applications

arXiv:2607.13218v1 Announce Type: cross 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 colon Eo N and a demand function wolon Vimes Vo N. Our main focus is the problem of finding a cut (S, ar{S}) minimizing the quantity [ psi_w( S ) = frac{c( S, ar{S} )}{w( S, V )dot w( ar{S}, V )}. ] Here, c( S, ar{S} ) is the cost of edges between S and the complement of S, ar{S}, and w( S, V )=w( S )+w( S, ar{S} ) is the sum of the internal demand within S, w( S ), and the demand between vertices of S and ar{S}, w( S, ar{S} ). We call psi_w( S ) the generalized conductance of the cut (S, ar{S}), and the task of minimizing psi_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 Gsetminus C, w( H )leq rhodot 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.

Source: arXiv cs.LG | 2026-07-16