Spectral sparsification limits revealed for directed graphs beyond cut balance
Beyond Cut Balance: Spectral Sparsification of the Nonlinear Directed Laplacian
Data Structures and Algorithms
Summary
The paper studies how to simplify complex directed graphs while approximately preserving certain energy measurements related to flow and direction. The authors show that even when a graph's edges are perfectly balanced between directions, it can still require a surprisingly large number of edges to accurately keep this energy. However, for a special kind of directed graph called a tournament, they prove good simplifications are possible without balance assumptions. Their results reveal unexpected limitations and possibilities in graph simplification related to direction and flow.
What this means in practice
- •For network designers: Optimize directed network models by knowing when spectral sparsification efficiently preserves flow-related energy.
- •For optimization engineers: Use spectral sparsifiers to approximate quadratic cost of nonnegative flows efficiently in directed systems.
A theory result. No direct application yet.
Authors
Yuichi Yoshida
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.