Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper extends the classification of locally checkable labeling (LCL) problems to unbounded degree graphs by introducing Local PMSO (LPMSO) problems, which can be defined using Presburger monadic second-order formulas. The authors demonstrate that the previously established complexity gaps of $ω(\log n)$ to $n^{o(1)}$ and $ω(n^{1/(k+1)})$ to $o(n^{1/k})$ also apply to LPMSO problems on unbounded degree rooted trees, maintaining the decidability of these gaps. This advancement not only broadens the applicability of LCL problems but also enriches the theoretical landscape by allowing for a more comprehensive understanding of complexity in graph problems.
Complexity gaps in locally checkable labeling problems extend to unbounded degree graphs, revealing new insights into their decidability.
The last decade of research on the LOCAL model has seen tremendous progress in understanding locally checkable labeling (LCL) problems, culminating in an almost complete classification of the possible complexities LCL problems can exhibit. In particular, on undirected trees, Chang and Pettie showed that there is no LCL problem with complexity between $ω(\log n)$ and $n^{o(1)}$ and Chang showed that, for every positive integer $k$, there is no LCL problem with complexity between $ω(n^{1/(k+1)})$ and $o(n^{1/k})$; additionally, which side of each gap a problem is found on is decidable. While the class of LCL problems - which, roughly speaking, consists of problems for which the correctness of a solution can be described by a finite set of allowed node configurations, which in turn can be locally verified by a constant-time algorithm - includes many important problems, it has one major restriction: problems can be defined only on bounded degree graphs, which consequently restricts all the classification and gap results mentioned above. In this work, we propose a generalization of LCL problems to unbounded degree using Presburger monadic second-order (PMSO) formulas; more specifically, we consider what we call Local PMSO (LPMSO) problems, i.e., problems whose correct solutions are both finitely described by a PMSO formula and locally verifiable by a LOCAL algorithm in constant time - this class contains many of the important problems studied in the LOCAL model but defines them on unbounded degree graphs. As our main result we prove that, on unbounded degree rooted trees, the aforementioned $ω(\log n)$ - $n^{o(1)}$ and $ω(n^{1/(k+1)})$ - $o(n^{1/k})$ complexity gaps (and their decidability) extend to the class of LPMSO problems.