Subgraph sparsification and nearly optimal ultrasparsifiers
Subgraph sparsification and nearly optimal ultrasparsifiers
We consider a variation of the spectral sparsification problem where we are required to keep a subgraph of the original graph. Formally, given a union of two weighted graphs G and W and an integer k, we are asked to find a k-edge weighted graph Wk such that G+Wk is …