Subgraph Sparsification and Nearly Optimal Ultrasparsifiers

Understand

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 $W_k$ such that $G+W_k$ is a good spectral sparsifer of $G+W$.
• We will refer to this problem as the subgraph (spectral) sparsification.
• We present a nontrivial condition on $G$ and $W$ such that a good sparsifier exists and give a polynomial time algorithm to find the sparsifer.