Subgraph Sparsification and Nearly Optimal Ultrasparsifiers

Alexandra Kolla, Yury Makarychev, Amin Saberi +1

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$ an…