Learning Centre

Distributed graph problems through an automata-theoretic lens

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.author Chang, Yi Jun
dc.contributor.author Studený, Jan
dc.contributor.author Suomela, Jukka
dc.date.accessioned 2023-03-15T07:10:46Z
dc.date.available 2023-03-15T07:10:46Z
dc.date.issued 2023-03-24
dc.identifier.citation Chang , 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.113710 en
dc.identifier.issn 0304-3975
dc.identifier.other PURE UUID: f538d9c3-d669-4506-bb87-66b4aa911033
dc.identifier.other PURE ITEMURL: https://research.aalto.fi/en/publications/f538d9c3-d669-4506-bb87-66b4aa911033
dc.identifier.other PURE LINK: http://www.scopus.com/inward/record.url?scp=85148698479&partnerID=8YFLogxK
dc.identifier.other PURE FILEURL: https://research.aalto.fi/files/103090485/SCI_Chang_etal_TCS_2023.pdf
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/120112
dc.description Publisher Copyright: © 2023 The Author(s)
dc.description.abstract The 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.format.mimetype application/pdf
dc.language.iso en en
dc.publisher ELSEVIER SCIENCE B.V.
dc.relation.ispartofseries Theoretical Computer Science en
dc.relation.ispartofseries Volume 951 en
dc.rights openAccess en
dc.title Distributed graph problems through an automata-theoretic lens en
dc.type A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä fi
dc.description.version Peer reviewed en
dc.contributor.department National University of Singapore
dc.contributor.department Department of Computer Science
dc.contributor.department Computer Science Professors
dc.contributor.department Department of Computer Science en
dc.subject.keyword Algorithm synthesis
dc.subject.keyword Automata theory
dc.subject.keyword Computational complexity
dc.subject.keyword Distributed algorithms
dc.subject.keyword LCL problems
dc.subject.keyword LOCAL model
dc.identifier.urn URN:NBN:fi:aalto-202303152438
dc.identifier.doi 10.1016/j.tcs.2023.113710
dc.type.version publishedVersion

Files in this item

Files Size Format View

There are no open access files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search archive

Advanced Search

article-iconSubmit a publication