2017/11/17 by Alev, Vedat Levi, Anari, Nima, Lau, Lap Chi +1 · 5 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1711.06530
\def\vecc#1\boldsymbol#1 We design a polynomial time algorithm that for any weighted undirected graph G = (V, E,\vecc w) and sufficiently large δ> 1, partitions V into subsets V1, …, Vh for some h≥ 1, such that \bullet at most δ-1 fraction of the weights are between clusters, i.e. w(E - ∪i = 1h E(Vi)) \lesssim \fracw(E)δ; \bullet the effective resistance diameter of each of the induced subgraphs G[Vi] is at most δ3 times the average weighted degree, i.e. maxu, v ∈ Vi ReffG[Vi](u, v) \lesssim δ3 ⋅ (|V|)/(w(E)) for all i=1, …, h. In particular, it is possible to remove one percent of weight of edges of any given graph such that each of the resulting connected components has effective resistance diameter at most the inverse of the average weighted degree. Our proof is based on a new connection between effective resistance and low conductance sets. We show that if the effective resistance between two vertices u and v is large, then there must be a low conductance cut separating u from v. This implies that very mildly expanding graphs have constant effective resistance diameter. We believe that this connection could be of independent interest in algorithm design.