There are several correspondences between matrices and graphs, e.g., each matrix is the adjacancy matrix of a weighted graph. The terms support preconditioner or combinatorial preconditioner refer to preconditioners which have been designed using graph theoretical tools that rely on these correspondences.
It certainly good to have another track of development besides, say, incomplete cholesky factorization or algebraic multigrid. But I wonder in which cases these preconditioners are superior to other usual preconditioners.
In recent paper, these preconditioners have been applied to finite element discretizations of scalar elliptic PDEs: Avron et al., Combinatorial preconditioners for scalar elliptic finite-elements problems. - As far as I understand, these preconditioners are outperformed by Incomplete Cholesky factorization, but on the other hand are very well-behaved in the presence of degenerated elements or very anisotropic coefficient tensors.
What are the applications where these preconditioners are most promising?