Ruoxu Cen

FOCS Conference 2025 Conference Paper

Fast Algorithms for Graph Arboricity and Related Problems

• Ruoxu Cen
• Henry L. Fleischmann
• George Zhaoqi Li
• Jason Li 0006
• Debmalya Panigrahi

We give an algorithm for finding the arboricity of a weighted, undirected graph, defined as the minimum number of spanning forests that cover all edges of the graph, in $\sqrt{n} m^{1+o(1)}$ time. This improves on the previous best bound of $\tilde{O}(nm)$ for weighted graphs and $\tilde{O}\left(\mathrm{~m}^{3/2}\right)$ for unweighted graphs (Gabow 1995) for this problem. The running time of our algorithm is dominated by a logarithmic number of calls to a directed global minimum cut subroutine – if the running time of the latter problem improves to $m^{1+o(1)}$ (thereby matching the running time of maximum flow), the running time of our arboricity algorithm would improve further to $m^{1+o(1)}$. We also give a new algorithm for computing the entire cut hierarchy – laminar multiway cuts with minimum cut ratio in recursively defined induced subgraphs – in $m n^{1+o(1)}$ time. The cut hierarchy yields the ideal edge loads (Thorup 2001) in a fractional spanning tree packing of the graph which, we show, also corresponds to a max-entropy solution in the spanning tree polytope. For the cut hierarchy problem, the previous best bound was $\tilde{O}\left(n^{2} m\right)$ for weighted graphs and $\tilde{O}\left(n m^{3/2}\right)$ for unweighted graphs.

STOC Conference 2025 Conference Paper

Network Unreliability in Almost-Linear Time

• Ruoxu Cen
• Jason Li 0006
• Debmalya Panigrahi

SODA Conference 2024 Conference Paper

Beyond the Quadratic Time Barrier for Network Unreliability

• Ruoxu Cen
• William He
• Jason Li 0006
• Debmalya Panigrahi

STOC Conference 2024 Conference Paper

Hypergraph Unreliability in Quasi-Polynomial Time

• Ruoxu Cen
• Jason Li 0006
• Debmalya Panigrahi

The hypergraph unreliability problem asks for the probability that a hypergraph gets disconnected when every hyperedge fails independently with a given probability. For graphs, the unreliability problem has been studied over many decades, and multiple fully polynomial-time approximation schemes are known starting with the work of Karger (STOC 1995). In contrast, prior to this work, no non-trivial result was known for hypergraphs (of arbitrary rank). In this paper, we give quasi-polynomial time approximation schemes for the hypergraph unreliability problem. For any fixed ε ∈ (0, 1), we first give a (1+ε)-approximation algorithm that runs in m O (log n ) time on an m -hyperedge, n -vertex hypergraph. Then, we improve the running time to m · n O (log 2 n ) with an additional exponentially small additive term in the approximation.

SODA Conference 2023 Conference Paper

Steiner Connectivity Augmentation and Splitting-off in Poly-logarithmic Maximum Flows

• Ruoxu Cen
• William He
• Jason Li 0006
• Debmalya Panigrahi

We give an almost-linear time algorithm for the Steiner connectivity augmentation problem: given an undirected graph, find a smallest (or minimum weight) set of edges whose addition makes a given set of terminals τ-connected (for any given τ > 0). The running time of our algorithm is dominated by polylogarithmic calls to any maximum flow subroutine; using the recent almost-linear time maximum flow algorithm (Chen et al. , FOCS 2022), we get an almost-linear running time for our algorithm as well. This is tight up to the polylogarithmic factor even for just two terminals. Prior to our work, an almost-linear (in fact, near-linear) running time was known only for the special case of global connectivity augmentation, i. e. , when all vertices are terminals (Cen et al. , STOC 2022). We also extend our algorithm to the closely related Steiner splitting-off problem, where the edges incident on a vertex have to be split-off while maintaining the (Steiner) connectivity of a given set of terminals. Prior to our work, a nearly-linear time algorithm was known only for the special case of global connectivity (Cen et al. , STOC 2022). The only known generalization beyond global connectivity was to preserve all pairwise connectivities using a much slower algorithm that makes n calls to an all-pairs maximum flow (or Gomory-Hu tree) subroutine (Lau and Yung, SICOMP 2013), as against polylog( n ) calls to a (single-pair) maximum flow subroutine in this work. * Ruoxu Cen and Debmalya Panigrahi were supported in part by NSF grants CCF-1750140 (CAREER Award) and CCF-1955703.

SODA Conference 2022 Conference Paper

Augmenting Edge Connectivity via Isolating Cuts

• Ruoxu Cen
• Jason Li 0006
• Debmalya Panigrahi

We give an algorithm for augmenting the edge connectivity of an undirected graph by using the isolating cuts framework (Li and Panigrahi, FOCS ‘20). Our algorithm uses poly-logarithmic calls to any max-flow algorithm, which yields a running time of Õ ( m + n 3/2 ) and improves on the previous best time of Õ ( n 2 ) (Benczúr and Karger, SODA ‘98) for this problem. We also obtain an identical improvement in the running time of the closely related edge splitting off problem in undirected graphs.

STOC Conference 2022 Conference Paper

Edge connectivity augmentation in near-linear time

• Ruoxu Cen
• Jason Li 0006
• Debmalya Panigrahi

We give an Õ( m )-time algorithm for the edge connectivity augmentation problem and the closely related edge splitting-off problem. This is optimal up to lower order terms and closes the long line of work on these problems.

FOCS Conference 2021 Conference Paper

Minimum Cuts in Directed Graphs via Partial Sparsification

• Ruoxu Cen
• Jason Li 0006
• Danupon Nanongkai
• Debmalya Panigrahi
• Thatchaphol Saranurak
• Kent Quanrud

We give an algorithm to find a minimum cut in an edge-weighted directed graph with $n$ vertices and $m$ edges in $\tilde{O}(n\cdot\max\{m^{2/3}, \ n\})$ time. This improves on the 30 year old bound of $\tilde{O}(nm)$ obtained by Hao and Orlin for this problem. Using similar techniques, we also obtain $\tilde{O}(n^{2}/\epsilon^{2})$ -time $(1+{\epsilon})$ -approximation algorithms for both the minimum edge and minimum vertex cuts in directed graphs, for any fixed $\epsilon$. Before our work, no (1 + $\epsilon)$ -approximation algorithm better than the exact runtime of $\tilde{O}(nm)$ is known for either problem. Our algorithms follow a two-step template. In the first step, we employ a partial sparsification of the input graph to preserve a critical subset of cut values approximately. In the second step, we design algorithms to find the (edge/vertex) mincut among the preserved cuts from the first step. For edge mincut, we give a new reduction to $\tilde{O}(\min\{{n}/m^{1/3}, \sqrt{n}\}){-}$ calls of any maxflow subroutine, via packing arborescences in the sparsifier. For vertex mincut, we develop new local flow algorithms to identify small unbalanced cuts in the sparsified graph.