Graph Multi-partitioning and Higher Order Cheeger Inequalities; Anand Louis - Georgia Tech

Опубликовано 27 июля 2016, 0:39

Cheeger's fundamental inequality states that any edge-weighted graph has a vertex subsetS such that its expansion (a.k.a. conductance ofS or the sparsity of the cut(S,S ?) ) is bounded as follows: ?(S)=w(S,S ? )/(w(S))??(2?_2 ), where w is the total edge weight of a subset or a cut and?_2 is the second smallest eigenvalue of the normalized Laplacian of the graph. I will talk about some natural generalizations of the sparsest cut in a graph: 1. a partition of the vertex set intok parts that minimizes the sparsity of the partition (defined as the ratio of the weight of edges between parts to the total weight of edges incident to the smallestk-1 parts); 2. a partition of the vertex set intok partsS_1,�,S_k that minimizemax i?[k])?(S_i); 3. a subset of sizeO(1/k) of the graph with minimum expansion. I will present some extensions of Cheeger's classical inequality to these problems via higher eigenvalues of the graph Laplacian and some approximation-algorithms for them. In particular, for the sparsestk-partition, we prove that the sparsity is at most8?(?_k ) log k where?k is the k-th smallest eigenvalue of the normalized Laplacian matrix. For the k sparse cuts problem we prove that there exist ck disjoint subsetsS1,�,S(1-?)k, such that maxi?(S_i )?C ??_k logk whereC0 are suitable absolute constants; this leads to a similar bound for the small-set expansion problem, namely for anyk, there is a subsetS whose weight is at most aO(1/k) fraction of the total weight and?(S)? C ??_k logk. The latter two results are the best possible in terms of the eigenvalues up to constant factors. Our results are derived via simple and efficient algorithms, and can themselves be viewed as generalizations of Cheeger's method. Based on joint works with Prasad Raghavendra, Prasad Tetali and Santosh Vempala.