Abstract:
Distributed graph algorithms solve problems that are related to the structure of an unknown communication graph. Each node of the graph is a computer. Initially, each node is only aware of the edges incident to it, but it can learn more about the structure of the graph by exchanging messages with its neighbours. Eventually, each node has to stop and produce a local output. The local outputs constitute a solution of a graph problem: for example, if we study the vertex cover problem, each node produces one bit of local output, indicating whether it is part of the vertex cover.
We define that the running time of a distributed algorithm is the number of communication rounds until all nodes have stopped. The key question is which graph problems can be solved fast with a distributed algorithm. Our recent work has settled many open questions in this area. In this talk, I will give a brief overview of a few selected results, both old and new.
I will focus on lower bounds, i.e., results that show what cannot be solved fast with any distributed algorithm. One such result is related to the classical graph problem of finding a small vertex cover. On bipartite graphs, maximum matching and minimum vertex cover are dual problems; by König's theorem, the size of a maximum matching equals the size of a minimum vertex cover. It is known that maximum matching on low-degree bipartite graphs can be approximated arbitrarily well with a very fast distributed algorithm, and it would be natural to expect that the same holds for the dual problem as well. However, we show that this is not the case: even if we study bipartite graphs of maximum degree 3, finding a 1.01-approximation of a minimum vertex cover requires at least logarithmic time.
About the speaker:
Jukka Suomela (http://users.ics.aalto.fi/suomela/) received his PhD from the University of Helsinki in 2009. He is a Docent in Computer Science at the University of Helsinki, and he was recently appointed as an Assitant Professor in the Department of Information and Computer Science at Aalto University, starting from 1 January 2014. His current research focuses on the foundations of distributed computing.
Last updated on 3 Dec 2013 by Antti Ukkonen - Page created on 3 Dec 2013 by Antti Ukkonen