  We propose a path cover adaptive algebraic multigrid (PC-$\alpha$AMG) method
for solving linear systems of weighted graph Laplacians and can also be applied
to discretized second order elliptic partial differential equations. The
PC-$\alpha$AMG is based on unsmoothed aggregation AMG (UA-AMG). To preserve the
structure of smooth error down to the coarse levels, we approximate the level
sets of the smooth error by first forming vertex-disjoint path cover with paths
following the level sets. The aggregations are then formed by matching along
the paths in the path cover. In such manner, we are able to build a multilevel
structure at a low computational cost. The proposed PC-$\alpha$AMG provides a
mechanism to efficiently re-build the multilevel hierarchy during the
iterations and leads to a fast nonlinear multilevel algorithm. Traditionally,
UA-AMG requires more sophisticated cycling techniques, such as AMLI-cycle or
K-cycle, but as our numerical results show, the PC-$\alpha$AMG proposed here
leads to nearly optimal standard V-cycle algorithm for solving linear systems
with weighted graph Laplacians. Numerical experiments for some real world graph
problems also demonstrate PC-$\alpha$AMG's effectiveness and robustness,
especially for ill-conditioned graphs.
