M.Sc Student | Levy Rina |
---|---|

Subject | Fast Distributed Approximation for Max-Cut |

Department | Department of Computer Science |

Supervisors | Professor Keren Censor-Hillel |

Professor Hadas Shachnai |

Finding a maximum cut is a fundamental problem in theoretical computer science. A cut in an undirected graph is a bipartition of the vertices, whose size is the number of edges crossing the bipartition. As Max-Cut is known to be NP-hard, the main focus is on finding approximation algorithms for the problem. Although the problem has been widely studied in many models, surprisingly, it has been insufficiently studied in the classic distributed settings.

In this thesis we consider a distributed network of n computational entities that is modeled by a graph. The vertices, which represent the entities, communicate by synchronously sending messages to their neighbours over their adjacent edges. As communication is more expensive than local computation, we assume that the computational power of each vertex is unlimited, and the complexity of the algorithms is measured as the number of communication rounds they require. This is the classic distributed model known as the LOCAL model. We also consider the more restricted CONGEST model, in which the size of the messages is bounded to O(log(n)).

It is well known that a 1/2-approximation can be obtained easily by simply choosing a random cut, and therefore, can be obtained in our model without communication. On the other hand, a single vertex can find an optimal solution, once it has learned the underlying graph. However, this requires O(n) communication rounds even in the relaxed LOCAL model. This defines a tradeoff between time complexity and the approximation ratio obtained by distributed Max-Cut algorithms, which raises the following natural question: How well can Max-Cut be approximated in the distributed setting, using a bounded number of communication rounds?

To the best of our knowledge, this
question has been studied in our distributed models only for a restricted graph
class. The contribution of this thesis is in amending the current
unsatisfactory state of affairs, by developing two key techniques for
approximating Max-Cut. We present *clustering-based* and *coloring-based*
approaches for addressing the problem.

In the clustering-based approach, we first apply a low-diameter decomposition on the graph, and then solve the problem optimally within each connected component. The technique leads to a (1-epsilon)-approximation algorithm for Max-Cut in both directed and undirected graphs, using O(log(n)/epsilon) communication rounds in the LOCAL model.

In the coloring-based approach, we
first color the graph to obtain independent sets of vertices. Then, we iterate
through each color class and let the vertices make their greedy decisions in
parallel. The technique provides deterministic 1/2-approximation and
1/3-approximation algorithms for Max-Cut and Max-Dicut, respectively, and a
randomized 1/2-approximation algorithm for Max-Dicut. Each of these algorithms
requires O^{~}(Delta ?*(n)) communication rounds in the CONGEST
model.

Finally, we combine both of the
methods to achieve fast deterministic approximation algorithms for Max-Cut and
Max-Dicut, by solving the problem separately for vertices of low degree using
coloring and for vertices of high degree using clustering. We obtain
deterministic algorithms with approximation ratios of 1/2 and 1/3 for Max-Cut
and Max-Dicut, respectively, requiring min{O^{~}(Delta ?*(n)),O(sqrt(n))}
communication rounds in the LOCAL model.