Sparsifier subgraphs

From Egres Open
Jump to: navigation, search

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]


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


  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