Distributed Symmetry Breaking on Power Graphs via Sparsification
| dc.contributor | Aalto-yliopisto | fi |
| dc.contributor | Aalto University | en |
| dc.contributor.author | Maus, Yannic | en_US |
| dc.contributor.author | Peltonen, Saku | en_US |
| dc.contributor.author | Uitto, Jara | en_US |
| dc.contributor.department | Department of Computer Science | en |
| dc.contributor.groupauthor | Computer Science Professors | en |
| dc.contributor.groupauthor | Computer Science - Algorithms and Theoretical Computer Science (TCS) | en |
| dc.contributor.groupauthor | Professorship Uitto J. | en |
| dc.contributor.organization | Graz University of Technology | en_US |
| dc.contributor.organization | Department of Computer Science | en_US |
| dc.date.accessioned | 2023-08-30T04:19:44Z | |
| dc.date.available | 2023-08-30T04:19:44Z | |
| dc.date.issued | 2023-06-19 | en_US |
| dc.description | Funding Information: Saku Peltonen is supported by the Academy of Finland, Grant 334238. Publisher Copyright: © 2023 Owner/Author(s). | |
| dc.description.abstract | In this paper we present efficient distributed algorithms for classical symmetry breaking problems, maximal independent sets (MIS) and ruling sets, in power graphs. We work in the standard CONGEST model of distributed message passing, where the communication network is abstracted as a graph G. Typically, the problem instance in CONGEST is identical to the communication network G, that is, we perform the symmetry breaking in G. In this work, we consider a setting where the problem instance corresponds to a power graph Gk, where each node of the communication network G is connected to all of its k-hop neighbors.A β-ruling set is a set of non-adjacent nodes such that each node in G has a ruling neighbor within β hops; a natural generalization of an MIS. On top of being a natural family of problems, ruling sets (in power graphs) are well-motivated through their applications in the powerful shattering framework [BEPS JACM'16, Ghaffari SODA'19] (and others). We present randomized algorithms for computing maximal independent sets and ruling sets of Gk in essentially the same time as they can be computed in G. Our main contribution is a deterministic poly(k, log n) time algorithm for computing k-ruling sets of Gk, which (for k > 1) improves exponentially on the current state-of-the-art runtimes. Our main technical ingredient for this result is a deterministic sparsification procedure which may be of independent interest.We also revisit the shattering algorithm for MIS [BEPS J'ACM'16] and present different approaches for the post-shattering phase. Our solutions are algorithmically and analytically simpler (also in the LOCAL model) than existing solutions and obtain the same runtime as [Ghaffari SODA'16]. | en |
| dc.description.version | Peer reviewed | en |
| dc.format.extent | 11 | |
| dc.format.extent | 157-167 | |
| dc.format.mimetype | application/pdf | en_US |
| dc.identifier.citation | Maus, Y, Peltonen, S & Uitto, J 2023, Distributed Symmetry Breaking on Power Graphs via Sparsification . in PODC 2023 - Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing . ACM, pp. 157-167, ACM Symposium on Principles of Distributed Computing, Orlando, Florida, United States, 19/06/2023 . https://doi.org/10.1145/3583668.3594579 | en |
| dc.identifier.doi | 10.1145/3583668.3594579 | en_US |
| dc.identifier.isbn | 9798400701214 | |
| dc.identifier.other | PURE UUID: 195e8b08-6f7f-4443-bc70-ae4fed184e97 | en_US |
| dc.identifier.other | PURE ITEMURL: https://research.aalto.fi/en/publications/195e8b08-6f7f-4443-bc70-ae4fed184e97 | en_US |
| dc.identifier.other | PURE LINK: http://www.scopus.com/inward/record.url?scp=85163923920&partnerID=8YFLogxK | en_US |
| dc.identifier.other | PURE FILEURL: https://research.aalto.fi/files/119689680/SCI_Maus_etal_PODC_2023.pdf | en_US |
| dc.identifier.uri | https://aaltodoc.aalto.fi/handle/123456789/122958 | |
| dc.identifier.urn | URN:NBN:fi:aalto-202308305298 | |
| dc.language.iso | en | en |
| dc.relation.ispartof | ACM Symposium on Principles of Distributed Computing | en |
| dc.relation.ispartofseries | PODC 2023 - Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing | en |
| dc.rights | openAccess | en |
| dc.subject.keyword | CONGEST model | en_US |
| dc.subject.keyword | distributed algorithm | en_US |
| dc.subject.keyword | maximal independent set | en_US |
| dc.subject.keyword | power graphs | en_US |
| dc.subject.keyword | ruling sets | en_US |
| dc.subject.keyword | shattering | en_US |
| dc.subject.keyword | sparsification | en_US |
| dc.title | Distributed Symmetry Breaking on Power Graphs via Sparsification | en |
| dc.type | A4 Artikkeli konferenssijulkaisussa | fi |
| dc.type.version | publishedVersion |
