טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentLevy Rina
SubjectFast Distributed Approximation for Max-Cut
DepartmentDepartment of Computer Science
Supervisors Professor Keren Censor-Hillel
Professor Hadas Shachnai


Abstract

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.