Distributed Half-Integral Matching and Beyond

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorDahal, Sameepen_US
dc.contributor.authorSuomela, Jukkaen_US
dc.contributor.departmentDepartment of Computer Scienceen
dc.contributor.editorRajsbaum, Sergioen_US
dc.contributor.editorBalliu, Alkidaen_US
dc.contributor.editorOlivetti, Dennisen_US
dc.contributor.editorDaymude, Joshua J.en_US
dc.contributor.groupauthorComputer Science Professorsen
dc.contributor.groupauthorComputer Science - Large-scale Computing and Data Analysis (LSCA)en
dc.contributor.groupauthorComputer Science - Algorithms and Theoretical Computer Science (TCS)en
dc.contributor.groupauthorProfessorship Suomela J.en
dc.contributor.organizationDepartment of Computer Scienceen_US
dc.date.accessioned2023-08-01T06:16:29Z
dc.date.available2023-08-01T06:16:29Z
dc.date.embargoinfo:eu-repo/date/embargoEnd/2024-05-25en_US
dc.date.issued2023en_US
dc.description.abstractBy prior work, it is known that any distributed graph algorithm that finds a maximal matching requires Ω(log∗n) communication rounds, while it is possible to find a maximal fractional matching in O(1) rounds in bounded-degree graphs. However, all prior O(1)-round algorithms for maximal fractional matching use arbitrarily fine-grained fractional values. In particular, none of them is able to find a half-integral solution, using only values from {0,12,1}. We show that the use of fine-grained fractional values is necessary, and moreover we give a complete characterization on exactly how small values are needed: if we consider maximal fractional matching in graphs of maximum degree Δ=2d, and any distributed graph algorithm with round complexity T(Δ) that only depends on Δ and is independent of n, we show that the algorithm has to use fractional values with a denominator at least 2d. We give a new algorithm that shows that this is also sufficient.en
dc.description.versionPeer revieweden
dc.format.extent18
dc.format.extent339-356
dc.format.mimetypeapplication/pdfen_US
dc.identifier.citationDahal, S & Suomela, J 2023, Distributed Half-Integral Matching and Beyond . in S Rajsbaum, S Rajsbaum, A Balliu, D Olivetti & J J Daymude (eds), Structural Information and Communication Complexity - 30th International Colloquium, SIROCCO 2023, Proceedings . Lecture Notes in Computer Science, vol. 13892, Springer, pp. 339-356, International Colloquium on Structural Information and Communication Complexity, Madrid, Spain, 06/06/2023 . https://doi.org/10.1007/978-3-031-32733-9_15en
dc.identifier.doi10.1007/978-3-031-32733-9_15en_US
dc.identifier.isbn978-3-031-32732-2
dc.identifier.isbn978-3-031-32733-9
dc.identifier.issn0302-9743
dc.identifier.issn1611-3349
dc.identifier.otherPURE UUID: 0bb27cf1-a941-44a6-950b-4453eaf3a28fen_US
dc.identifier.otherPURE ITEMURL: https://research.aalto.fi/en/publications/0bb27cf1-a941-44a6-950b-4453eaf3a28fen_US
dc.identifier.otherPURE LINK: http://www.scopus.com/inward/record.url?scp=85163292063&partnerID=8YFLogxKen_US
dc.identifier.otherPURE FILEURL: https://research.aalto.fi/files/116861394/Distributed_Half_Integral_Matching_and_Beyond.pdfen_US
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/122148
dc.identifier.urnURN:NBN:fi:aalto-202308014509
dc.language.isoenen
dc.publisherSpringer
dc.relation.ispartofInternational Colloquium on Structural Information and Communication Complexityen
dc.relation.ispartofseriesStructural Information and Communication Complexity - 30th International Colloquium, SIROCCO 2023, Proceedingsen
dc.relation.ispartofseriesLecture Notes in Computer Scienceen
dc.relation.ispartofseriesVolume 13892en
dc.rightsopenAccessen
dc.titleDistributed Half-Integral Matching and Beyonden
dc.typeConference article in proceedingsfi
dc.type.versionacceptedVersion
Files