The Distributed Complexity of Locally Checkable Labeling Problems Beyond Paths and Trees

Yi-Jun Chang

We consider locally checkable labeling LCL problems in the LOCAL model of distributed computing. Since 2016, there has been a substantial body of work examining the possible comple…