Beyond Cut Balance: Spectral Sparsification of the Nonlinear Directed Laplacian
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 QG+(x)=∑(u,v)∈ Ewuv(xu−xv)+2, (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 QG+(x) within a factor of 1±ε simultaneously for all x∈ℝ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 Θ̃(n3/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 Õ(n/ε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 QG+ also preserves, for every feasible demand vector, the optimum quadratic cost of a nonnegative flow. Hence the guarantee contains information beyond directed cut values.
Related
- Canonical Directed Laplacian on F_2^4, Symmetry-Induced Two-Scale Coupling, and the Structural Isomorphism of a 64-Copy Boolean Graph Assembly
- Power-Type Nonlinear Schrödinger Equations with the Logarithmic Laplacian
- Existence of solutions for a nonlinear elliptic equation involving (p(x),q(x))-Laplacian and (p(x),q(x))-biharmonic Operator
- Spectral geometry of the magnetic p-Laplacian
- Spectral Γ2 inequalities for the V-Laplacian with evolving weighted measures
BibTeX
@misc{yoshida2026beyond,
title = {{Beyond Cut Balance: Spectral Sparsification of the Nonlinear Directed Laplacian}},
author = {Yuichi Yoshida},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08177},
eprint = {2609.08177},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08177},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Beyond Cut Balance: Spectral Sparsification of the Nonlinear Directed Laplacian
AU - Yuichi Yoshida
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.08177
UR - https://arxiv.org/abs/2609.08177
AB - 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)=∑_(u,v)∈ Ew_uv(x_u−x_v)_+^2, (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±ε simultaneously for all x∈ℝ^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 Θ̃(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 Õ(n/ε^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.
ER -