Faster Cluster Decomposition with Stronger Bi-Criteria Guarantee

Partitioning the vertex set of a graph $G=(V,E)$ into clusters is a classical problem in computer science. As vertices within clusters should be well connected and cuts between clusters sparse, Oveis Gharan and Trevisan (SODA 2014, [OGT14]) proposed to measure the partition quality using inner and outer conductance, i.e., the bi-criteria guarantee. Specifically, when partitioning V into vertex-disjoint subsets P₁,…, Pₖ, every subgraph induced by Pᵢ should have high conductance, while the conductance of Pᵢ in G should be low. They studied the existence of such a partition and designed a polynomial-time algorithm achieving this guarantee. For more than a decade, their algorithm remained the only one achieving this guarantee on its output clusters. In this paper, we study faster cluster decomposition algorithms under the same setup as [OGT14] and prove three results: 1. We make their existential result algorithmic: Our algorithms run in nearly-linear time, and achieve the same bi-criteria guarantee as the one in [OGT14] up to constant factors, including the asymptotically tight dependence on k. 2. We prove that their existential result holds algorithmically under a much weaker condition on the initial disjoint subsets. To achieve this, we develop a general algorithm framework that boosts the approximation guarantee of a solution: given an $α$-approximate solution to the k-way conductance problem, if ρG(k+1)/ρG(k)=Ω(α/ε), then a (1+ε)-approximate solution can be obtained using only O(k(1+logα)) minimum s-t cut computations. 3. We present a nearly-linear time algorithm that finds clusters with the bi-criteria guarantee. Our algorithm has the same guarantee as the one in [OGT14], which, for any unweighted graph of n vertices and m edges, runs in O(knm²) time.