{"id":"arxiv/2609.08177","url":"https://arxiv.org/abs/2609.08177","tags":["cs.DS","math.SP"],"score":0,"title":"Beyond Cut Balance: Spectral Sparsification of the Nonlinear Directed Laplacian","domain":"cs.DS","source":"arxiv","authors":["Yuichi Yoshida"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-08","reactions":{}}