Distributed symmetry breaking in graphs with bounded diversity

Leonid Barenboim, Tzalik Maimon

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء


We consider the distributed synchronous message passing model, also known as the LOCAL model. In this model the input graph G represents a network, where each vertex in the graph is a processor and each edge is a communication line between two processors. Symmetry breaking problems are among the most studied problems in this model [4], [7], [9]-[11], [13], [17], [18], [23], [24], [26]. In this paper we devise a general method for solving symmetry breaking problems in graphs with bounded diversity. Roughly speaking, the diversity of a graph is the maximum number of maximal cliques a vertex belongs to. This general method uses a new approach which utilizes a structure called a connector. We build a series of such connectors, each of which simplifies the previous one by decreasing maximum clique size. Eventually, cliques becomes sufficiently small and have some additional properties that allow us to bound the maximum degree of the connectors. Then it becomes possible to employ efficient symmetry-breaking algorithms for bounded-degree graphs and extend the results to all the connectors in the series in backward order, until we reach a solution for the original graph. We use the ideas of this general method to achieve the following results. First, we devise an improved algorithm for maximal matching with running time of O(log(S)(D(G) + log∗ n)), where D(G) is the diversity of G and S(G) is the maximum clique size. The best currently-known deterministic result for general graphs is O(log2 ? log n) [13]. This result is also the best currently-known for graphs with bounded diversity, hence our result constitutes an improvement for graphs with D(G) = o(log ? log n). Another algorithm of ours for the same problem has a running time of O(D(G)2 + log∗ n). For graphs with D(G) = O(1) this shows a separation of complexities between the maximal matching problem and the maximal independent set problem. Indeed, in such graphs our algorithm computes a maximal matching within O(log n) time, while computing a maximal independent set requires ?( (log n / log log n)) time. This is the first result for any family of graphs that shows that maximal matching is provably easier than maximal independent set in the distributed setting. Moreover, using the same methods, we devise improved algorithms for ruling sets in graphs with bounded diversity. We also obtain an improved result for the wider family of graphs with bounded neighborhood independence ?. Specifically, we compute a maximal matching within O(? log ?+log∗ n) time in such graphs.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفProceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018
ناشرInstitute of Electrical and Electronics Engineers Inc.
عدد الصفحات10
رقم المعيار الدولي للكتب (المطبوع)9781538643686
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 3 أغسطس 2018
الحدث32nd IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018 - Vancouver, كندا
المدة: ٢١ مايو ٢٠١٨٢٥ مايو ٢٠١٨

سلسلة المنشورات

الاسمProceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018


!!Conference32nd IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018

ملاحظة ببليوغرافية

Publisher Copyright:
© 2018 IEEE.


أدرس بدقة موضوعات البحث “Distributed symmetry breaking in graphs with bounded diversity'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا