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
