# Sparsifier subgraphs

Devise combinatorial polynomial-time algorithms for the following two problems.

• Given a graph G, find a subgraph H with $O(n)$ edges such that $d_H(X) \geq \Omega(\frac{n}{m}) d_G(X)$ for every $X \subseteq V$
• Given a graph G, find a subgraph H with $\Omega(n)$ edges such that $d_H(X) \leq O(\frac{n}{m}) d_G(X)$ for every $X \subseteq V$

## Remarks

For both properties, the existence of H can be derived from the following theorem, which is a corollary of a result in [1] on spectral sparsifiers (which is in turn based on [2]).

Theorem. Let G=(V,E) be an undirected graph, $w:E \to {\mathbb R}_+$ a weight function, and $E_1,\dots,E_n$ a partition of E into n parts. There exists $F \subseteq E$ of cardinality $O(n)$ and a weight function $z:F \to {\mathbb R}_+$ such that the following two properties hold.

• $\sum_{e \in E_i} w_e \leq \sum_{e \in F \cap E_i} z_e \leq \frac{3}{2}\sum_{e \in E_i} w_e$ for every $i$,
• $d_w(X) \leq d_z(X) \leq \frac{3}{2}d_w(X)$ for every $X \subseteq V$.

To obtain the two desired statements, let $w(e)=1$ for every $e \in E$, and let $E_1,\dots,E_n$ be an arbitrary partition of E into n parts such that $|E_i|-|E_j| \leq 1$ for every $i,j$. Let F be the subgraph given by the theorem. It can be seen (see e.g. [3]) that H=F satisfies the first property, while taking H as the n/2 edges in F with highest z values satisfies the second property.

## References

1. M.K. de Carli Silva, N.J.A. Harvey, C.M. Sato, Sparse sums of positive semidefinite matrices, arXiv link
2. J. Batson, D.A. Spielman, N. Srivastava, Twice-Ramanujan Sparsifiers, arXiv link, DOI link
3. W.M. Hoza, L.J. Schulman, The Adversarial Noise Threshold for Distributed Protocols, arXiv link