Title: Inapproximability and Every-Case Complexity of the Distributed Minimum Spanning Tree Problem

Speaker: Michael Elkin, Institute for Advanced Study, Princeton

Date: Tuesday, February 25, 4:30-5:30PM

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

We study the minimum-weight spanning tree (MST) problem in the distributed model of computation. In this model each vertex of the input n-vertex graph G hosts a processor, and each processor has infinite computational power, but its initial knowledge of the graph is very limited. Specifically, each vertex v knows the identities of its neighbors, and the weights of the edges that are incident to v. The vertices are allowed to communicate through the edges of the graph. The communication is synchronous, and occurs in discrete rounds. The goal is to minimize the number of rounds of distributed computation, which is henceforth referred as the running time.

The MST problem is one of the most fundamental and well-studied problems in the area of distributed computing. Nearly matching upper and lower bounds are known for this problem. We improve both upper and lower bounds, and furthermore, we initiate the study of the approximability of distributed problems. Specifically, we show that for any $0 < \eps < 1$ computing $n^{1-\eps}$-approximate MST requires $\Omega(n^{\eps/2})$ time even on graphs of small unweighted diameter. Denoting the approximation ratio by H and the time complexity by T, the result can be interpreted as an unconditional lower bound on the time-approximation tradeoff, $T^2 \cdot H = \Omega(n)$. We also generalize this tradeoff to the MST problem restricted to graphs with diameter at most (a possibly constant) $\Lambda$ (the exponent of T becomes roughly $2 + 1/\Lambda$ instead of 2).

We also come up with a new complexity measure, every-case complexity. This measure is more delicate than its traditional worst-case and average-case counteraparts, but it is applicable only to problems that can be solved in sublinear time, such as distributed MST problem. We study the every-case complexity of the distributed MST problem, and identify an explicit graph parameter, that we call MST-radius, that reflects to a very large extent the every-case complexity of the problem. In particular, we devise a every-case optimal algorithm for the MST problem, and show a tight lower bound on the possible running time of any correct algorithm.

The presentation is based on a very recent manuscript called "Inapproximability and Every-Case Complexity of the Distributed Minimum Spanning Tree Problem", authored by the speaker.