CS Paper Radar

Faster Cluster Decomposition with Stronger Bi-Criteria Guarantee

He Sun, Yong Zhang, Yacong Zhou

cs.DS ·submitted 2026-11-04 06:01 UTC · v1
theory

Abstract

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_1,\ldots, P_k$, every subgraph induced by $P_i$ should have high conductance, while the conductance of $P_i$ 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)=Ω\left(α/\varepsilon\right)$, then a $(1+\varepsilon)$-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 $\widetilde{O}(knm^2)$ time.

Comment
41 pages, 3 figures, 1 table

Closest papers

Nearest neighbours by meaning across the whole index.

Fully Dynamic Correlation Clustering with Vertex Updates in Polylogarithmic Update Time

cs.DS ·2026-11-06 ·Vladimir Braverman, Prathamesh Dharangutte, Chenglin Fan, Chen Wang, Shenghao Xie +1 more
similarity 0.65
Abstract

We present a fully dynamic algorithm for correlation clustering that supports \emph{vertex} insertions and deletions while maintaining an $O(1)$ approximation in polylogarithmic amortized update time. This resolves an open problem of vertex deletions posed by a recent line of work on dynamic correlation clustering. We adopt the min-disagreement objective for correlation clustering, i.e., given a signed complete graph $G=(V,E^+\cup E^-)$, we want to minimize the total number of $(+)$ edge crossing clusters and $(-)$ edges within clusters. The input is given in the adjacency list model, where each update inserts or deletes a node along with its full set of $(+)$ neighbors. Our main technical contribution is a fault-tolerant sparse-dense decomposition framework which unlike the existing decomposition-based frameworks allows for structural inconsistencies as long as the induced cost is bounded. We also show a separation between explicitly maintaining the (stronger) sparse-dense decomposition and maintaining a constant-factor approximation to correlation clustering, which may be of independent interest.

0.28

A Simple Active-Set Method for PageRank-Based Local Graph Clustering

cs.DS ·2026-08-17 ·Zhewei Wei, Mingji Yang
similarity 0.62
Abstract · 17 pages

Local graph clustering aims to find a well-connected cluster near a given seed node without exploring the entire graph. A key step in the classic local clustering algorithm of Andersen, Chung, and Lang (ACL; Internet Math. 2007) is to approximate the PageRank vector from the seed node. Their local push method computes an ACL $\varepsilon$-approximate PageRank vector with teleportation parameter $α$ in $O\bigl(1/(α\varepsilon)\bigr)$ time. We give an algorithm that computes an ACL $\varepsilon$-approximate PageRank vector in $\widetilde{O}\bigl(1 / \varepsilon^2\bigr)$ time with high probability. This bound is independent of the graph size and has only a polylogarithmic dependence on $1 / α$, albeit with a quadratic dependence on $1 / \varepsilon$. As a direct consequence, we obtain a new running-time tradeoff between the target conductance and target volume in local graph clustering. Our method also applies to the optimization problem of $\ell_1$-regularized PageRank and computes an additive approximate minimizer with a polylogarithmic dependence on $1/α$, improving the $1/\sqrtα$ dependence in the previous bound of Martínez-Rubio, Wirth, and Pokutta (COLT 2023). Our algorithm is based on an intuitive process that maintains a growing active set of nodes: it performs push operations on the current set until convergence and then expands the set and repeats the process if necessary. We show that for each active set, the corresponding limiting state is the solution to a symmetric diagonally dominant (SDD) linear system on the set. We apply nearly-linear-time SDD solvers to these systems and prove that the approximation preserves the properties of the push process.

0.47

Competitive Random-Order Correlation k-Clustering

cs.DS ·2026-09-28 ·Mahsa Derakhshan, Andisheh Ghasemi, Rajmohan Rajaraman, Omer Wasim, Tegan Wilson
theory similarity 0.60
Abstract · 58 pages, 5 figures, 1 table

Correlation clustering has been extensively studied over the last two decades in many different computational models owing to its wide-ranging practical applications. The goal is to compute a partition of the vertex set such that the total number of disagreements, i.e. the sum of edges between clusters, and non-edges within clusters, is minimized. In this paper, we study correlation $k$-clustering, in which the total number of clusters is restricted to $k$. Correlation $k$-clustering is NP-hard, and while previous work has presented a polynomial time approximation scheme for constant $k$, there are no known results for general $k$. Our first result is a polynomial-time constant-factor approximation algorithm for correlation $k$-clustering for general $k$. The main focus of this work is in the more challenging online setting. Noting that the best competitive ratio under adversarial arrivals is known to be $Ω(n)$, we concentrate on the well-studied random-order model, where vertices arrive in random order and on arrival of a vertex, edges to its earlier-arrived neighbors are revealed. We prove a surprising lower bound of $Ω(\log k)$-competitiveness for any online algorithm, which can be extended to $Ω(\log n)$ when $k = \text{poly}(n)$. Finally, the main result of this paper is a polylogarithmic upper bound on the competitive ratio for correlation $k$-clustering, using an algorithm inspired by the classic Pivot algorithm for correlation clustering. All theorems have been verified using Lean.

0.19

Introvert Clustering for Distributed Graph Algorithms

cs.DC cs.DS ·2026-09-09 ·Yi-Jun Chang, Nima Dolatabadi
similarity 0.60
Abstract

We introduce a graph decomposition primitive called introvert clustering, which strengthens standard low-diameter clustering by guaranteeing that every clustered vertex keeps at least a $\left(\frac12-\varepsilon\right)$-fraction of its relevant neighbors in its own cluster. Repeatedly applying this primitive yields a layered introvert network decomposition with $O(\log n)$ layers and weak diameter $O(\log n)$. We give two applications in the $\mathsf{LOCAL}$ model. For every constant $\varepsilon>0$, we obtain a $\widetilde O(\log^2 n)$-round deterministic algorithm for list $\left(\frac32+\varepsilon\right)Δ$-edge coloring on graphs of maximum degree $Δ\geqΔ_0(\varepsilon)$; for bipartite graphs, the result holds for all $Δ$. For every constant $0<\varepsilon<1/4$, we also obtain a $\widetilde O(\log^2 n)$-round deterministic algorithm for a $\left(\frac14-\varepsilon\right)$-locally balanced cut, where every vertex has at least a $\left(\frac14-\varepsilon\right)$-fraction of its neighbors on the opposite side. The resulting algorithms are remarkably simple: edge coloring processes the layers in reverse order and colors each cluster, while locally balanced cut processes them forward and computes a locally maximum cut within each cluster. The introvert guarantee enables these procedures beyond the usual greedy regime of network decomposition. We construct the decomposition in $O(\log^2 n)$ randomized rounds using Miller--Peng--Xu low-diameter clustering and a simple trimming procedure, and deterministically in $\widetilde O(\log^2 n)$ rounds via a white-box adaptation of the recursive network decomposition algorithm of Ghaffari and Grunau [FOCS 2024].

0.26

Pseudometric-Weighted Correlation Clustering via Spectral Preclustering

cs.DS ·2026-09-15 ·Chenglin Fan, Dahoon Lee, Euiwoong Lee
similarity 0.59
Abstract · 37 pages, 2 figures, in submission

We study \emph{pseudometric-weighted correlation clustering}, in which pairs have arbitrary positive or negative labels and nonnegative disagreement weights satisfying the triangle inequality. For every fixed $\varepsilon>0$, we give a randomized polynomial-time $(2+\varepsilon)$-approximation, improving the previous factor of $10/3$. The algorithm constructs an explicit feasible solution to the cluster LP with polynomial support and value at most $(1+\varepsilon)\mathrm{OPT}$, where $\mathrm{OPT}$ is the minimum integral clustering cost. Our main contribution is a weighted preclustering construction that witnesses a near-optimal clustering while bounding the total weight of admissible edges by $\operatorname{poly}(1/\varepsilon)\mathrm{OPT}$. We obtain admissibility certificates from random walks, where the factor-two Ptolemy's inequality for pseudometrics reduces the required length of walks from $O(\log n)$ to a constant. We then bound the rounding error separately at each vertex and use the triangle inequality to control its weighted cost. Sampling and coverage corrections produce an exactly feasible solution, and the factor-two rounding completes the approximation algorithm.

0.37

The Complexity of Weak Partition Connectivity in Hedgegraphs

cs.DS math.CO ·2026-09-14 ·Yuanhao Wang, Wei Wang
theory similarity 0.59
Abstract

We prove that deciding whether the weak partition connectivity (WPC) of an unweighted hedgegraph is at most a given integer is NP-complete, resolving an open question about its computational complexity. Hardness holds even for connected full-support split systems, where each hedge consists of two nonempty, vertex-disjoint hyperedges covering all vertices. We also obtain hardness on connected edge-colored simple graphs in which each color class is a spanning forest with exactly two nontrivial trees. On both classes, exact computation of fractional WPC is NP-hard, whereas hedge connectivity is computable exactly in polynomial time. A binary matrix formulation yields the reduction and a deterministic polynomial-time exact algorithm under a linear intersection condition on row supports after normalization and column compression. In particular, both integer and fractional WPC are computable in polynomial time when these supports have size at most two, whereas NP-hardness holds already when their size is bounded by three. For every fixed $b$, we give deterministic and randomized efficient polynomial-time approximation schemes on hedgegraphs in which each hedge has at most $b$ connected components, counting isolated vertices. Both schemes return one partition that simultaneously approximates integer and fractional WPC. Unless $\mathrm P=\mathrm{NP}$, neither objective admits a deterministic FPTAS, even on the two hard instance classes.

0.13

Parameterized Complexity of Edge-Constrained Graph Partitioning

cs.DS cs.CC ·2026-08-28 ·Ajinkya Gaikwad, Jan Pokorný, Tomáš Valla
similarity 0.59
Abstract

We study the Edge-Constrained Graph Partitioning Problem (ECGP), which asks whether the vertices of a graph can be partitioned into r parts, each inducing at least gamma edges. We also consider a balanced variant (BECGP), requiring equal-sized parts, and signed variants, where the utility of a part is the difference between its numbers of positive and negative edges. We show that ECGP and BECGP remain NP-hard for fixed gamma, while BECGP is also NP-hard for fixed r. For the natural parameterization r+gamma, both problems admit polynomial kernels. We obtain FPT algorithms for ECGP and BECGP parameterized by maximum leaf number, vertex deletion distance to a clique, cluster vertex deletion number plus gamma, and vertex integrity. Furthermore, ECGP is FPT parameterized by vertex deletion distance to stars plus gamma and vertex deletion distance to paths plus gamma. On the negative side, ECGP and BECGP are W[1]-hard when parameterized by r together with several structural parameters. In particular, hardness holds for feedback edge set, vertex deletion distance to stars or paths, and modular width even when the corresponding parameter is zero. The problems are also W[1]-hard parameterized by cluster vertex deletion number plus r, and by clique-width even when gamma=3. For signed graphs, both variants are NP-hard even when r+gamma=3 and the input is a disjoint union of two cliques. Finally, the balanced signed variant is W[1]-hard parameterized by treedepth plus r, even when gamma=0.

0.09

Hermite Brings a Laptop: Analyzing Frieze-Jerrum Rounding Yields Improved Approximations for Clustering Problems

cs.DS ·2026-09-28 ·David García-Soriano, Atsushi Miyauchi
similarity 0.59
Abstract

The Frieze-Jerrum rounding is a standard tool for rounding SDP relaxations of graph partitioning and clustering problems, assigning nodes to at most $k$ clusters using $k$ independent Gaussian vectors. Its analysis hinges on the collision probability $P_k(ρ)$ that two nodes whose SDP vectors have inner product $ρ$ are assigned to the same cluster. No tractable closed form for $P_k$ is known for $k\geq 4$, making it difficult to certify approximation guarantees and hindering the systematic search for better algorithms. We develop a Hermite-coefficient certification framework to derive accurate and tractable bounds on $P_k$. Using the Hermite expansion of Gaussian noise stability, we express $P_k$ as a power series with nonnegative coefficients, reduce these coefficients to one-dimensional Gaussian integrals, and certify finitely many of them, yielding rigorous bounds on $P_k$ over the entire correlation range. Our framework yields strengthened polynomial-time approximations for several clustering problems. For MaxAgree Correlation Clustering, we derive a $0.7818$-approximation, the first improvement in two decades over the $0.7666$ ratio of Swamy (2004). We also improve the best known ratios for the variant with at most $K$ clusters, MaxAgree$[K]$ (e.g., from $0.77$ to $0.8151$ for $K=3$). For Max $K$-Cut we resolve, via a structural property of the Hermite expansion, a conjecture of de Klerk et al. (2004) characterizing the Frieze--Jerrum approximation ratio for every $K\ge3$; we show that this ratio is tight, and determine it to within $10^{-6}$ accuracy for $K\le16$. Finally, we reduce the additive approximation error for modularity maximization from $0.42084$ (Kawase et al., 2021) to $0.3790$. On the hardness side, we show that approximating Maxagree within $0.802+ε$ is Unique Games-hard via a construction in Gaussian space analyzed by Borell's inequality.

0.40