# Sparsifier subgraphs

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

- Given a graph
*G*, find a subgraph H with [math]O(n)[/math] edges such that [math]d_H(X) \geq \Omega(\frac{n}{m}) d_G(X)[/math] for every [math]X \subseteq V[/math] - Given a graph
*G*, find a subgraph H with [math]\Omega(n)[/math] edges such that [math]d_H(X) \leq O(\frac{n}{m}) d_G(X)[/math] for every [math]X \subseteq V[/math]

## 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, [math]w:E \to {\mathbb R}_+[/math] a weight function, and [math]E_1,\dots,E_n[/math] a partition of *E* into *n* parts. There exists [math]F \subseteq E[/math] of cardinality [math]O(n)[/math] and a weight function [math]z:F \to {\mathbb R}_+[/math] such that the following two properties hold.

- [math]\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[/math] for every [math]i[/math],
- [math]d_w(X) \leq d_z(X) \leq \frac{3}{2}d_w(X)[/math] for every [math]X \subseteq V[/math].

To obtain the two desired statements, let [math]w(e)=1[/math] for every [math]e \in E[/math], and let [math]E_1,\dots,E_n[/math] be an arbitrary partition of *E* into *n* parts such that [math]|E_i|-|E_j| \leq 1[/math] for every [math]i,j[/math]. 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.

## Related conjectures

Goddyn's conjecture on thin spanning trees

## References

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