  In this paper, we study a posteriori error estimators which aid multilevel
iterative solvers for linear systems with graph Laplacians. In earlier works
such estimates were computed by solving global optimization problems, which
could be computationally expensive. We propose a novel strategy to compute
these estimates by constructing a Helmholtz decomposition on the graph based on
a spanning tree and the corresponding cycle space. To compute the error
estimator, we solve efficiently the linear system on the spanning tree, and
then we solve approximately a least-squares problem on the cycle space. As we
show, such an estimator has a nearly-linear computational complexity for sparse
graphs under certain assumptions. Numerical experiments are presented to
demonstrate the efficacy of the proposed method.
