  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 complexities of LCL problems. For example, it has been
established that there are no LCL problems exhibiting deterministic
complexities falling between $\omega(\log^* n)$ and $o(\log n)$. This line of
inquiry has yielded a wealth of algorithmic techniques and insights that are
useful for algorithm designers.
  While the complexity landscape of LCL problems on general graphs, trees, and
paths is now well understood, graph classes beyond these three cases remain
largely unexplored. Indeed, recent research trends have shifted towards a
fine-grained study of special instances within the domains of paths and trees.
  In this paper, we generalize the line of research on characterizing the
complexity landscape of LCL problems to a much broader range of graph classes.
We propose a conjecture that characterizes the complexity landscape of LCL
problems for an arbitrary class of graphs that is closed under minors, and we
prove a part of the conjecture.
  Some highlights of our findings are as follows.
  1. We establish a simple characterization of the minor-closed graph classes
sharing the same deterministic complexity landscape as paths, where $O(1)$,
$\Theta(\log^* n)$, and $\Theta(n)$ are the only possible complexity classes.
  2. It is natural to conjecture that any minor-closed graph class shares the
same complexity landscape as trees if and only if the graph class has bounded
treewidth and unbounded pathwidth. We prove the "only if" part of the
conjecture.
  3. In addition to the well-known complexity landscapes for paths, trees, and
general graphs, there are infinitely many different complexity landscapes among
minor-closed graph classes.

Distributed, Parallel, and Cluster Computing;Data Structures and Algorithms