Graph Partitioning with Demands: Generalized Conductance and its Applications

Abstract: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<\rho<\eta<1$, we give a polynomial-time bi-criteria algorithm for GPD whose components have demand at most $\eta \cdot W$ and cost at most $\mathcal{O}_{\rho,\eta}(\sqrt{\log n})$ times the optimum cost for threshold~$\rho$. This procedure can then be applied recursively to obtain an $\mathcal{O}(\sqrt{\log 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+\epsilon)$-approximation in $n^{O(1/\rho)}$ time. Moreover, through previous reduction, these GPD algorithms yield a $\frac{4e}{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-\epsilon$ by reduction from Vertex Cover, while HCD is hard to approximate within a factor of $1.0748$, by reduction from Min-Sum Vertex Cover.

Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG)

arXiv:2607.13218 [cs.DS]

(or arXiv:2607.13218v2 [cs.DS] for this version)

https://doi.org/10.48550/arXiv.2607.13218 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.