Distributed graph problems through an automata-theoretic lens

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorChang, Yi Junen_US
dc.contributor.authorStudený, Janen_US
dc.contributor.authorSuomela, Jukkaen_US
dc.contributor.departmentDepartment of Computer Scienceen
dc.contributor.groupauthorComputer Science Professorsen
dc.contributor.groupauthorComputer Science - Algorithms and Theoretical Computer Science (TCS)en
dc.contributor.groupauthorComputer Science - Large-scale Computing and Data Analysis (LSCA)en
dc.contributor.groupauthorProfessorship Suomela J.en
dc.contributor.organizationNational University of Singaporeen_US
dc.date.accessioned2023-03-15T07:10:46Z
dc.date.available2023-03-15T07:10:46Z
dc.date.issued2023-03-24en_US
dc.descriptionPublisher Copyright: © 2023 The Author(s)
dc.description.abstractThe locality of a graph problem is the smallest distance T such that each node can choose its own part of the solution based on its radius-T neighborhood. In many settings, a graph problem can be solved efficiently with a distributed or parallel algorithm if and only if it has a small locality. In this work we seek to automate the study of solvability and locality: given the description of a graph problem Π, we would like to determine if Π is solvable and what is the asymptotic locality of Π as a function of the size of the graph. Put otherwise, we seek to automatically synthesize efficient distributed and parallel algorithms for solving Π. We focus on locally checkable graph problems; these are problems in which a solution is globally feasible if it looks feasible in all constant-radius neighborhoods. Prior work on such problems has brought primarily bad news: questions related to locality are undecidable in general, and even if we focus on the case of labeled paths and cycles, determining locality is PSPACE-hard (Balliu et al., PODC 2019). We complement prior negative results with efficient algorithms for the cases of unlabeled paths and cycles and, as an extension, for rooted trees. We study locally checkable graph problems from an automata-theoretic perspective by representing a locally checkable problem Π as a nondeterministic finite automaton M over a unary alphabet. We identify polynomial-time-computable properties of the automaton M that near-completely capture the solvability and locality of Π in cycles and paths, with the exception of one specific case that is co-NP-complete.en
dc.description.versionPeer revieweden
dc.format.mimetypeapplication/pdfen_US
dc.identifier.citationChang, Y J, Studený, J & Suomela, J 2023, ' Distributed graph problems through an automata-theoretic lens ', Theoretical Computer Science, vol. 951, 113710 . https://doi.org/10.1016/j.tcs.2023.113710en
dc.identifier.doi10.1016/j.tcs.2023.113710en_US
dc.identifier.issn0304-3975
dc.identifier.otherPURE UUID: f538d9c3-d669-4506-bb87-66b4aa911033en_US
dc.identifier.otherPURE ITEMURL: https://research.aalto.fi/en/publications/f538d9c3-d669-4506-bb87-66b4aa911033en_US
dc.identifier.otherPURE LINK: http://www.scopus.com/inward/record.url?scp=85148698479&partnerID=8YFLogxKen_US
dc.identifier.otherPURE FILEURL: https://research.aalto.fi/files/103090485/SCI_Chang_etal_TCS_2023.pdfen_US
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/120112
dc.identifier.urnURN:NBN:fi:aalto-202303152438
dc.language.isoenen
dc.publisherELSEVIER SCIENCE B.V.
dc.relation.ispartofseriesTheoretical Computer Scienceen
dc.relation.ispartofseriesVolume 951en
dc.rightsopenAccessen
dc.subject.keywordAlgorithm synthesisen_US
dc.subject.keywordAutomata theoryen_US
dc.subject.keywordComputational complexityen_US
dc.subject.keywordDistributed algorithmsen_US
dc.subject.keywordLCL problemsen_US
dc.subject.keywordLOCAL modelen_US
dc.titleDistributed graph problems through an automata-theoretic lensen
dc.typeA1 Alkuperäisartikkeli tieteellisessä aikakauslehdessäfi
dc.type.versionpublishedVersion

Files