Sixth Cargese Workshop on Combinatorial Optimization September 17, 2015

In this last lecture we will discuss graph sparsification: approximating a graph by weighted sub-graphs of itself. Sparsifications techniques have been used to design fast algorithms for combinatorial or linear algebraic problems, as a rounding technique in approximation algorithms, and have moti-vated startling results in pure mathematics. 1 Spectral Sparsifiers Let G = (V,E) be a graph with V = {1,..., n}. Let ei be the ith standard basis vector. For an edge e = {u, v} ∈ E, let χe = eu − ev, where u and v are ordered arbitrarily. The Laplacian of G is LG = e∈E χeχ T e. We say that a graph H on vertex set V spectrally approximates G if (1 − )LH LG (1 + )LH. (1) If H obtained from G by assigning non-negative weights to the edges, we call H a spectral sparsifier of G. The number of edges in H is defined to be the number of non-zero weights. We will prove and discuss the following theorem. Theorem 1. Every graph G has a spectral sparsifier with O(n log n/2) edges. References: Spielman-Srivastava 2008. 1.1 Sparsifiers preserve cuts For U ⊆ V, the set of edges in G with exactly one endpoint in U is denoted δ(U). A simple calculation shows that |δ(U) | = 1TULG1U, where 1U is the characteristic vector of the set U. If H is a spectral sparsifier of G then (1) implies that (1 − )1TULH1U ≤ 1ULG1U ≤ (1 + )1ULH1U ∀U ⊆ V. That is, the total weight in H of all edges in δ(U) lies in [1 − , 1 + ] · |δ(U)|. Application for fast algorithms. Consider any problem whose solution is determined by the cuts of G, e.g., the minimum s-t cut problem. Let A be an algorithm for this problem. Instead of running A on G, let us run it on the sparsifier H obtained from Theorem 1. The cut output by A is within 1 + of a minimum s-t cut in G. Running A on H instead of G is typically faster because H has fewer edges. Similar ideas can be used to give faster algorithms for the sparsest cut problem, the max cut problem, etc