CS Paper Radar

Directed Singular-Value Sparsifiers with $O(n \log n/ε^2)$ Arcs

Emile Anand

cs.DS cs.DM ·submitted 2026-11-10 17:08 UTC · v1
theory

Abstract

Given an unweighted directed graph, a sparsifier is a nonnegative reweighting of original arcs that preserves every in-degree and out-degree exactly. In this work, we study singular-value sparsifiers, which are generalizations of spectral sparsifiers. Singular-value sparsifiers find a number of applications in theoretical computer science, such as maintaining directed cuts and flows, speeding up directed Laplacian solvers, and sparsifying dense weight matrices in neural networks. Strong singular-value (SV) approximation supports sparse representations of directed random walks with guarantees that remain stable under products, and controls bilinear error in the left and right Schur-complement metrics. We prove that every unweighted directed graph on $n$ vertices admits an $\varepsilon$-SV sparsifier with $O(n\log(2n)/\varepsilon^2)$ arcs, improving the $O(n\log^5 n/\varepsilon^2)$ support bound of Lau, Wang, and Zhou. The sparsifier is a nonnegative reweighting of original arcs and preserves every in-degree and out-degree exactly. We also give a randomized construction with $\tilde{O}(m+n)$ real-arithmetic running time, where $m$ is the input support size, and the output has the same support bound and rational weights of polynomial bit length.

Comment
44 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Beyond Cut Balance: Spectral Sparsification of the Nonlinear Directed Laplacian

cs.DS math.SP ·2026-09-08 ·Yuichi Yoshida
theory similarity 0.68
Abstract

Digraphs with constant cut balance admit nearly linear directed cut sparsifiers. This condition requires the total arc weights in the two directions of every cut to be within a constant factor of each other. We ask whether this condition also permits nearly linear spectral sparsification with respect to the energy of the nonlinear directed Laplacian. For a weighted digraph $G=(V,E,w)$, let \[ Q_G^+(x)=\sum_{(u,v)\in E}w_{uv}(x_u-x_v)_+^2, \qquad (t)_+:=\max\{t,0\}. \] This energy agrees with the outgoing-cut function on binary vectors. A spectral sparsifier is a nonnegatively reweighted subgraph that preserves $Q_G^+(x)$ within a factor of $1\pm\varepsilon$ simultaneously for all $x\in\mathbb R^V$. We show that cut balance alone does not yield nearly linear spectral sparsifiers: for constant error, the worst-case support size for simple unweighted Eulerian digraphs is $\widetildeΘ(n^{3/2})$, although Eulerian digraphs are perfectly cut-balanced and admit nearly linear directed cut sparsifiers. In contrast, we prove that every $n$-vertex tournament has a spectral sparsifier with $\widetilde O(n/\varepsilon^3)$ arcs, without any assumption on its cut balance. This includes the transitive tournament, whose cut balance is unbounded. Thus perfect balance does not guarantee nearly linear spectral sparsification, while unbounded imbalance does not preclude it. Finally, we use convex duality to show that preserving $Q_G^+$ also preserves, for every feasible demand vector, the optimum quadratic cost of a nonnegative flow. Hence the guarantee contains information beyond directed cut values.

0.16

Near-Optimal Space and Time Cut Sparsification in Turnstile Streams

cs.DS ·2026-11-02 ·Honghao Lin, Vahab Mirrokni, David P. Woodruff
similarity 0.64
Abstract

A seminal result of Ahn, Guha, and McGregor (PODS'12) showed that a cut sparsifier of an unweighted graph can be computed from a near-linear number of linear measurements. Later work extended this to spectral sparsifiers (Kapralov et al., FOCS'14) and to near-linear recovery time (Kapralov et al., SODA'20). For weighted graphs, these sketches rely on grouping edges by weight, which general turnstile streams do not allow. Chen, Khanna, and Li (FOCS'22) removed this limitation, using $\tilde{O}(n/\varepsilon^3)$ bits of space. We improve the space to $\tilde{O}(n/\varepsilon^2)$ bits. Our algorithm makes one pass over a general turnstile stream of a weighted graph, processes each update in $\tilde{O}(1)$ time, and recovers, in $\tilde{O}(n/\varepsilon^2)$ time, a reweighted subgraph with $O(n\varepsilon^{-2}\log^2 n)$ edges that preserves every cut within a factor of $1\pm\varepsilon$. Its space, update time, and recovery time are all optimal up to polylogarithmic factors.

0.24

Deterministic Spectral Sparsification in Almost-Linear Time for Dense Graphs

cs.DS ·2026-08-14 ·Jason Li, Trevor Vaughn
similarity 0.64
Abstract

A spectral sparsifier of a weighted graph is a reweighted subgraph whose Laplacian quadratic form approximates that of the original graph. Let $G$ be a positively weighted $n$-vertex, $m$-edge multigraph, let $0<\varepsilon\le1/2$. Assuming $m,\varepsilon^{-1}\le n^{O(1)}$ and the ratio of maximum to minimum weight is polynomially bounded, we deterministically construct a $(1\pm\varepsilon)$-spectral sparsifier with \[ O\!\left(n\varepsilon^{-2}\log^{24+o(1)}n\right) \] edges in \[ m^{1+o(1)}+O\!\left(n^2\varepsilon^{-9/2}\log^{113/2+o(1)}n\right) \] time. The construction has two main ingredients. First, we sparsify an approximately regular expander by partitioning its edges into few matchings and viewing their normalized Laplacians as an isotropic family of positive semidefinite matrices. Rather than sample from this family and apply matrix Chernoff, we select matchings deterministically using a pessimistic estimator. We evaluate the resulting conditional-expectation scores in two ways to produce two algorithms: using dense matrix multiplication and sparsely using polynomial approximations to the inverse square root and matrix exponential. Deterministic expander decomposition, along with replacing vertices by fixed expander graphs to achieve approximate regularity, extends these algorithms to general graphs. Second, a recursive blocking scheme applies the dense algorithm to smaller subgraphs and the sparse algorithm to their union, balancing their costs. Reusing the resulting algorithm as the dense algorithm gives $α_{r+1}=3-1/(α_r-1)$, starting from $α_0=ω$. After $O(\log n)$ levels, the exponent is $2+O(1/\log n)$, yielding $m^{1+o(1)}+\widetilde O_{\varepsilon}(n^2)$ time.

0.04

Graph Spectral Sparsification is in Catalytic Logspace

cs.DS cs.CC ·2026-08-21 ·Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld
similarity 0.64
Abstract · 29 pages

We give a catalytic logspace algorithm for the problem of graph spectral sparsification. Given an undirected graph $G$ on $n$ vertices and $\varepsilon>0$, our algorithm outputs an $\varepsilon$-spectral sparsifier of $G$ with $O(n\varepsilon^{-2}\log n)$ edges, matching the effective resistance sampling of Spielman and Srivastava (STOC 2008). This gives a new, natural problem in catalytic logspace that is not known to be in deterministic $\mathbf{NC}$ or $\mathbf{SC}$. Our main contribution is an entirely new technique in the compress--or--random paradigm for catalytic logspace that we believe will have further applications. We first analyze effective-resistance sparsification using a pessimistic estimator that can itself be computed in catalytic logspace. The estimator is motivated by the viewpoint of graph quasirandomness and immediately gives a simple, deterministic greedy algorithm for graph sparsification. Subsequently, we show that such a pessimistic estimator can be transformed into an algorithm that performs an in-place compression of a string with bad potential. Our algorithm is based on using the potential function to define a measure over strings, and implementing arithmetic coding using this measure in-place. This compression technique is substantially distinct from all prior tools in the field of catalytic computation.

0.20

Sparsification Framework for Directed Densest Subgraph

cs.DS ·2026-10-01 ·Slobodan Mitrović, Theodore Pan
similarity 0.62
Abstract

We develop a new approach for computing approximate directed densest subgraphs (DDS). Our main result is a sparsification procedure that reduces a directed graph $G$ on $n$ vertices to a graph with $n \cdot \text{poly} \log n$ edges while preserving enough structure to recover an approximate DDS of $G$. Instantiating this framework in several memory-constrained settings, we obtain the following improvements over the state of the art: In semi-streaming, we obtain a single-pass algorithm that computes a $(1-\varepsilon)$-approximate DDS. Previously, the only semi-streaming algorithm that computed a constant approximation of DDS was by Bahmani, Kumar, and Vassilvitskii (2012), providing a $0.5-\varepsilon$ approximation in $O(\log n)$ passes. Hence, our work completely closes the approximation gap between undirected and directed DS in the semi-streaming setting, matching the $(1-\varepsilon)$-approximate undirected DS algorithm by Esfandiari, Hajiaghayi, and Woodruff (2016). In the near-linear-memory MPC regime, we obtain an $O(1)$-round algorithm for $(1-\varepsilon)$-approximate DDS, improving over the $O(\sqrt{\log n})$-round $(0.5-\varepsilon)$-approximation algorithm of Mitrović and Pan (2024). In the sublinear-time setting, we obtain an algorithm using $\tilde{O}(n)$ time, space, and oracle queries to compute a $(1-\varepsilon)$-approximate DDS, improving over the $\tilde{O}(n^{1.5})$ time, space, and query algorithm of Esfandiari, Hajiaghayi, and Woodruff (2016).

0.08

CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs

cs.LG stat.MLmath.NA ·2026-09-08 ·Meher Chaitanya, Cameron Musco, Aristides Gionis
theory similarity 0.62
Abstract

Graph-data workloads such as diffusion estimation, ranking, semi-supervised learning, and network optimization often solve many Laplacian or symmetric diagonally dominant M-matrix (SDDM) systems with the same coefficient matrix. Approximate Cholesky preconditioners eliminate vertices one at a time and store the resulting sparse approximate factorization, the \emph{factor}, whose construction cost is amortized across these solves. But eliminating a vertex, the \emph{pivot}, creates a dense Schur-complement clique among its $d$ active neighbors. We introduce CAST (Canonical Approximate Schur Tree), which replaces this clique with a weighted random spanning tree sampled directly from it. Every realization is connected and contains exactly d-1 edges, while reweighting each selected edge by the reciprocal of its tree-inclusion probability makes the update unbiased. The distribution is independent of the ordering of the pivot neighbors, and we prove that its leverage-score marginals minimize the largest normalized reweighted-edge contribution among unbiased inverse-marginal one-tree estimators. We also introduce CAST-$ρ$, which replaces each pivot neighbor with $ρ$ copies, each carrying a $1/ρ$ share of that neighbor's incident weight, samples a weighted random spanning tree on the expanded clique, and contracts the copies back to the original neighborhood. The resulting update remains unbiased and connected, can be sampled exactly in $O(ρd)$ time, and satisfies a $1/ρ$ bound on the second moment of the normalized local Schur error. Increasing $ρ$ therefore reduces certified local sampling variability, but may increase construction cost and downstream fill. Empirically, we observe that CAST-1 is the faster default, whereas CAST-2 is preferable when its additional edge contributions remain inexpensive.

0.43

Partially-Dynamic All-Pairs Maxflow and Effective Resistance via Stable Sparsifiers

cs.DS ·2026-08-26 ·Gramoz Goranci, Rasmus Kyng, Maximilian Probst Gutenberg, Yibin Zhao, Gernot Zöcklein
similarity 0.60
Abstract

We give a randomized data structure for undirected weighted graphs that are partially dynamic, i.e., that undergo either only edge insertions or only edge deletions. The data structure maintains $(1\pmε)$-approximations to the maxflow value and effective resistance between any queried pair of vertices, with total update time $\widetilde{O}_ε(n^2)$ and worst-case query time $\widetilde{O}_ε(1)$. Thus, for dense graphs where $m = Ω(n^2)$, our guarantees are near-optimal. Our algorithms succeed with high probability against an adaptive adversary. Our result follows from a simple stability principle for partially dynamic graphs. We show how to partition an online sequence of $m$ updates into $\widetilde{O}(n/ε)$ epochs such that every graph within an epoch is a $(1\pm O(ε))$-spectral approximation of the graph at the beginning of the epoch. The epochs are determined by the cumulative leverage score of the updated edges: small leverage-score mass implies small spectral change, while the total leverage-score mass over a monotone update sequence is $\widetilde{O}(n)$. Consequently, a spectral sparsifier needs to be recomputed only once per epoch. Applying known static all-pairs maxflow and effective-resistance oracles to these sparsifiers then yields the result.

0.09

A Deterministic Near-Linear Time Approximation Algorithm for Restricted Shortest Paths in Directed Graphs

cs.DS ·2026-10-13 ·Vikrant Ashvinkumar
similarity 0.60
Abstract · More detailed AI statement. Polished exposition and fixed typos

In the restricted shortest paths problem, we are given an $n$-vertex $m$-edge directed graph $G$ whose edges are assigned two non-negative weights (or resources) called lengths and costs, a source vertex $s$, and a cost threshold $C$. The goal is to find, for each target vertex $t$, the length of the shortest $(s,t)$-path whose total cost is at most $C$. Ashvinkumar, Bernstein, and Karczmarz (SODA 2025) gave the first randomized bicriteria $(1+\varepsilon,1+\varepsilon)$-approximate algorithm on directed graphs running in sub-$mn$ time, answering a problem posed by Bernstein (SODA 2012). We substantially improve this on two fronts, supplying a deterministic bicriteria $(1+\varepsilon,1+\varepsilon)$-approximate algorithm running in near-linear time. Our approach straightforwardly generalizes to more than two resources. For $k$ resources, a deterministic $(1+\varepsilon_1,\ldots,1+\varepsilon_k)$-approximate algorithm running in near-linear time is possible, with $\varepsilon_1=\ldots=\varepsilon_k=\varepsilon$.

0.20