The Landscape of Distributed Complexities on Trees and Beyond

Abstract

We study the local complexity landscape of locally checkable labeling (LCL) problems on constant-degree graphs with a focus on complexities below log∗n. Our contribution is threefold: (1) Our main contribution is that we complete the classification of the complexity landscape of LCL problems on trees in the LOCAL model, by proving that every LCL problem with local complexity o (log∗n) has actually complexityO(1). This result improves upon the previous speedup result from o (log log∗n) to O(1) by [Chang, Pettie, FOCS 2017].(2) In the related LCA and VOLUME models [Alon, Rubinfeld, Vardi, Xie, SODA 2012, Rubinfeld, Tamir, Vardi, Xie, 2011, Rosenbaum, Suomela, PODC 2020],we prove the same speedup from o (log∗n) to O(1) for all constant-degree graphs.