Distributed Graph Problems Through an Automata-Theoretic Lens

Yi-Jun Chang, Jan Studený*, Jukka Suomela

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

2 Citations (Scopus)
1 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationStructural Information and Communication Complexity
Subtitle of host publication28th International Colloquium, SIROCCO 2021, Wrocław, Poland, June 28 – July 1, 2021, Proceedings
EditorsTomasz Jurdziński, Stefan Schmid
Number of pages31
ISBN (Electronic)978-3-030-79527-6
DOIs
Publication statusPublished - 28 Jun 2021
MoE publication typeA4 Article in a conference publication
EventInternational Colloquium on Structural Information and Communication Complexity - Online, Wroclaw, Poland
Duration: 28 Jun 20211 Jul 2021
https://sirocco2021.ii.uni.wroc.pl

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume12810
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Colloquium on Structural Information and Communication Complexity
Abbreviated titleSIROCCO
Country/TerritoryPoland
CityWroclaw
Period28/06/202101/07/2021
Internet address

Fingerprint

Dive into the research topics of 'Distributed Graph Problems Through an Automata-Theoretic Lens'. Together they form a unique fingerprint.

Cite this