Parallel Spectral Graph Sparsification via Low Diameter Decompositions

Rank-Independent Spectral Hypergraph Sparsification via Global-Dictionary Chaining

We show that every weighted hypergraph on $n$ vertices admits a spectral $\varepsilon$-sparsifier with $O(n\log n/\varepsilon^2)$ hyperedges, strengthening the independent STOC 2023 works of Lee and Jambulapati--Liu--Sidford by removing their rank dependence and answering Lee's open question on whether this loss is inherent. The key idea is global-dictionary chaining: after choosing clique edge weights with balanced effective resistances, every hyperedge seminorm is Lipschitz with respect to the same global-dictionary norm generated by normalized vertex-pair directions; the local rank complexity is thereby replaced by the Gaussian width of this common dictionary. Since these STOC 2023 works have become standard analytic primitives across a broad subsequent literature on spectral hypergraph sparsification and its variants, our rank-independent theorem sharpens many later guarantees that inherit their sampling bounds.

Scalable Graph Coreset Selection via Greedy Sampling

This work proposes a simple and effective column-selective graph sampling algorithm based on a minimum inner product greedy selection rule, well-suited for large-scale graphs where the full Laplacian cannot be stored in memory.

A Practical Parallel Algorithm for Expander Decompositions

Expander decompositions have recently been used in many breakthrough results that prove near-optimal theoretical bounds for hard graph problems but still remain impractical for real-world applications. The primary bottleneck is a heavy reliance on iterative max-flow computations, which introduce a prohibitive overhead. We address this bottleneck by introducing a work-efficient parallel algorithm for expander decompositions whose main cut-finding procedure requires no flow computations. Instead, it leverages random walks at the cost of a slightly higher number of inter-cluster edges. While this algorithm still occasionally requires flows in the "trimming" step, we present another algorithm for the variant of weak expander decompositions that operates entirely without flow computations. To demonstrate the validity of this new direction, we complement the analysis with a practical CUDA implementation. We evaluate its performance on a suite of real-world graphs and observe a significant speedup over an optimized sequential baseline. Furthermore, in a study of the downstream task of computing normalized cuts, we achieve competitive quality against a state-of-the-art strong-expander based implementation, while offering far superior scalability. Finally, we show that a weak expander decomposition for any target expansion Φ can be extracted from a hierarchical congestion approximator in linear time. Together with prior results, we obtain a parallelizable new scheme for computing weak expander decompositions in almost-linear time. Crucially, the running time is independent of Φ, which mitigates another weakness of recent algorithms, an expensive running time dependence on 1/Φ.

Convex Recoloring of General Graphs: Formulations, Polyhedra, and Computational Experiments

A vertex coloring of a graph is convex if the vertices of each color induce a connected subgraph. In the convex recoloring problem (CR), the goal is to find a convex coloring while minimizing the weight of recolored vertices, i.e., vertices assigned a color different from their original one. This problem was originally motivated by the study of phylogenetic trees in bioinformatics and is NP-hard even on paths. Most existing research focuses on trees, with only limited results available for general graphs. We advance the state of the art by developing exact solution methods for CR on general graphs. In particular, we propose four mixed-integer linear programming formulations, including a compact flow-based model and a representatives model, and design corresponding solution methods. We compare the polytopes associated with the linear relaxation of the proposed formulations. Computational experiments on benchmark instances and on new synthetic instances show that a branch-and-cut algorithm based on the representatives formulation performs best overall.

Partially-Dynamic Maximum Flow in Dense Graphs

Fixed-Threshold Peeling in Sublinear MPC: Round-Approximation Tradeoffs and Applications

A number of fundamental graph problems admit simple algorithms based on iterative peeling: repeatedly remove all vertices whose current degree is below a fixed threshold. This paradigm underlies algorithms for density-dependent edge orientation, density-dependent coloring, densest subgraph, and $k$-core decomposition. In this paper, we study these problems in the sub-linear MPC model and achieve the following round-approximation tradeoffs. For density-dependent edge orientation, given any integer $t>0$, we compute an orientation with maximum out-degree at most $(2+\epsilon)(t+1)\alpha(G)$ in $O(\lg^{1/(t+2)} n \cdot \operatorname{poly}(\lg \lg n))$ rounds, where $\alpha(G)$ denotes the minimum possible maximum out-degree of an orientation of $G$. In the $\operatorname{poly}(\lg\lg n)$-round regime, this gives an $O(\lg\lg n/\lg\lg\lg n)$-approximation, improving the approximation factor of the recent work by Ghaffari and Grunau [PODC 2025]. We obtain a similar improvement for density-dependent coloring. For densest subgraph, we obtain a $(4+\epsilon)$-approximation in $\widetilde O(\lg^{1/3} n)$ MPC rounds and a $(6+\epsilon)$-approximation in $\widetilde O(\lg^{1/4} n)$ MPC rounds. This improves the $\widetilde O(\sqrt{\lg n})$ round complexity of Ghaffari, Lattanzi, and Mitrovi\'c [ICML 2019] with a slightly larger approximation factor. This is the first $O(1)$-approximate algorithm for densest subgraph to break the $\Theta(\sqrt{\lg n})$ round-complexity barrier in the sub-linear MPC model. For $k$-core decomposition, given any integer $t>0$, we compute approximate coreness values within a factor of $(2+\epsilon)(t+1)$ in $O(\lg^{1/(t+2)} n \cdot \operatorname{poly}(\lg \lg n))$ MPC rounds for any integer $t>0$. This improves the $\widetilde O(\sqrt{\lg n})$ round complexity of Ghaffari, Lattanzi, and Mitrovi\'c [ICML 2019], again giving a round-approximation tradeoff.