9 Solve the compress problem on $P^{\prime}$

10 $N^{(i)}\leftarrow N^{(i-1)}\cup N$ $\triangleright$ Only for the analysis

11

12

Algorithm 5 Better Compress

######  Corollary 39.

When we replace the _Compress with Slack_ procedure in the decomposition
algorithm Algorithm 4 with the _Better Compress_ procedure, the algorithm will
still output a correct solution.

###### Proof.

We still remove all paths of length $4\ell+9$, have the exact same amount of
slack at the ends and propagate valid labelsets on $e_{l},e_{r}$ and
$P_{l},P_{r}$, as in the algorithm from Section 5.3. Note that these labelsets
are valid in the sense, that they are produced by $f_{\pi,\infty}$ and we
therefore get correctness from [19]. ∎

We essentially compute a different kind of $(\gamma,\ell,L)$-decomposition,
where the length of the compress paths is not required to be in
$[\ell,2\ell]$. Instead the paths must be at least $\ell$ long and can instead
be arbitrarily long. However for our analysis to work, all nodes in $N^{(i)}$
must be able to terminate in a constant number of rounds in expectation.

So if we find a nice way to solve to compress problem fast, we can apply it to
these long paths and improve on the node-averaged complexity.

######  Lemma 40.

Consider some LCL $\Pi$ with worst case complexity $O(\log n)$ and feasible
function $f_{\Pi,\infty}$. If there exists an algorithm $A$ solving the
compress problem such that _in expectation_ nodes only use $O(1)$ rounds. Then
there exists an algorithm $A^{\prime}$ solving $\Pi$ with node averaged
complexity $O(1)$.

###### Proof.

The new algorithm $A^{\prime}$ is obtained by replacing the _Compress with
Slack_ procedure Algorithm 2 with the new _Better Compress_ from Algorithm 5.
Because of Corollary 39 we get that the algorithm will be correct. Furthermore
nodes outside of the compress paths don’t have to wait for the compress
problem to be solved completely. We first compute $P_{l}$ and $P_{r}$ by
differentiating between two cases:

  * •

Case 1 $(\beta<3\ell+2)$: Then both endpoints can see the entire path and so
we choose $P_{l}=(v_{0},\ldots,v_{\ell})$ and
$P_{r}=(v_{\ell+2},\ldots,v_{\beta})$. We then have $N=\\{v_{\ell+1}\\}$ and
put $v_{\ell+1}$ in layer $V^{R}_{i,1}$ and the nodes in $P_{l}$ and $P_{r}$
into $V^{C}_{i-1}$ as usual.

  * •

Case 2 $(\beta\geq 3\ell+2)$: Then both endpoints $v_{0},v_{\beta}$ see that
the path is long enough and choose $P_{l}=(v_{0},\ldots,v_{\ell})$ and
$P_{r}=(v_{\beta-\ell},\ldots,v_{\beta})$ 999We don’t actually need to
differentiate between the ”left” and ”right” path, as both simply apply
$f_{\Pi,\infty}$. We immediately assign layers $V^{C}_{i-1}$ to $P_{l}$ and
$P_{r}$ and propagate the labelsets up through $e_{l}$ and $e_{r}$. We get
that $N=(v_{\ell+1},\ldots,v_{\beta-\ell-1})$.Since $\beta>3\ell+2$ we get
that $|N|>\ell+2$ and so by assigning $v_{\ell+1}$ and $v_{\beta-\ell-1}$ to
$V^{R}_{i,1}$, we get that
$|N\setminus\\{v_{\ell+1},v_{\beta-\ell-1}\\}|>\ell$. Clearly it would be
possible to separate the unassinged nodes in $N$ into paths of length
$[\ell,2\ell]$, so there exists a valid solution to the compress problem
$P=(P_{l},N,P_{r})$.

In the first case we are clearly already done, in the second case we split the
path in a way, such that we obtain a valid Compress Problem. Everything up
until this point takes only a constant number of rounds. We then use $A$ to
solve this compress problem $P=(P_{l},N,P_{r})$ and have that in expectation
nodes only use $O(1)$ rounds. Crucially since the labelsets on $e_{l}$ and
$e_{r}$ are already known after a constant number of rounds, the decomposition
algorithm does not need to wait for the compress problem to be solved. So the
decomposition algorithm still performs one iteration in $O(1)$ rounds. Now the
only key difference is that in the analysis of the original decomposition
algorithm we always solved the compress problem in a constant number of rounds
and therefore all of the nodes in $N$ did terminate after a constant number of
rounds. Instead $A$ only gives us the guarantee that the nodes in $N$
terminate after a constant number of rounds _in expectation_. It is however
trivial to follow the previous analysis and see that by linearity of
expectation in Lemmas 34, 36 and 37, we obtain randomized $O(1)$ node averaged
complexity. ∎

We now give an algorithm that solves the compress problem in a randomized way,
such that in expectation nodes are done after a constant number of rounds. We
don’t really do more than computing a $[\ell+1,2\ell+1]$ ruling set, but to
fill out the details of how we obtain valid output labels, we present the
entire analysis. In Algorithm 6 we first take care of the trivial case, where
the path is very short. We then proceed to have $O(\log n)$ executions of the
subroutine _Elect Maximums_ given in Algorithm 7 that computes a
$[\ell+1,2\ell+1]$ ruling set $Z$ and has nodes output valid labels for the
incident edges as soon as possible.

Input: $P=(P_{l},N,P_{r}),\ell,i-1,f_{\Pi,\infty}$

1 $v_{l},v_{r}\leftarrow$ the nodes adjacent to $P_{l},P_{r}$

2 Apply $f_{\Pi,\infty}$ to $P_{l}$ and $P_{r}$.

3 if  _$v_{l}=v_{r}$_ then

4 Then $N=\\{v_{l}\\}$

5 Now $v_{l}$ has only incoming edges and can compute its maximal class $B$
and terminate.

6 Terminate

7

8$Z\leftarrow\\{v_{l},v_{r}\\}$ $\triangleright$ $N$ must have size at least
$\ell+2$

9 $c\leftarrow O(1)$ $\triangleright$ chose $c$ for desired failure
probability

10 for  _$8\ell\cdot c\cdot\ln n$ times_ do

11 ElectMaximums($\ell,Z,f_{\Pi,\infty}$)

12

Algorithm 6 randomized Compress

######  Lemma 41.

In each execution of _Elect Maximums_ Algorithm 7, each active node joins $Z$
with probability at least $\frac{1}{8\ell}$.

###### Proof.

Consider some active node $u$. The decision whether or not $u$ will join $Z$
depends only on its random choice to become a candidate and its $\ell$ hop
neighborhood. Let $C=\\{v\in N\mid dist(u,v)\leq\ell\text{ and $v$ is
active}\\}$ be all of the nodes that are close enough to influence $u$’s
decision and that will also potentially become a candidate. Then the
probability that $u$ joins $Z$ is:

$\displaystyle Pr[u\text{ joins }Z]$ $\displaystyle=Pr[u\text{ is a
candidate}]\prod_{v\in C}Pr[v\text{ is no
candidate}]=\frac{1}{2\ell}\cdot(1-\frac{1}{2\ell})^{|C|}$
$\displaystyle\geq\frac{1}{2\ell}\cdot(1-\frac{1}{2\ell})^{2\ell}\geq\frac{1}{2\ell}\cdot(1-\frac{1}{2})^{2}\geq\frac{1}{8\ell}$

using that $|C|\leq 2\ell$ and $(1+\frac{x}{m})^{m}\geq 1+x$ when $m\geq
1,|x|\leq m$ for $m=\ell,x=-\frac{1}{2}$ ∎

######  Lemma 42.

One execution of _Elect Maximums_ Algorithm 7 needs at most $6\ell$ rounds.

###### Proof.

We will argue that none of the steps requires more information than the
$6\ell$ neighborhood.

  * •

For loop in Line 7: Nodes can decide to become active seeing only their $\ell$
hop neighborhood. To determine whether or not $u$ does not have other
candidates in its $\ell$ hop neighborhood, it needs to know the random bits
and the $\ell$ hop neighborhoods of all of its $\ell$ hop neighbors. So its
$2\ell$ neighborhood in total.

  * •

For loop in Line 7: For all nodes at distance at most $2\ell+1$, $z$ needs to
know whether or not they are in $Z$. Since these nodes might have only joined
in this execution of Elect Maximums, we need to additionally see the $2\ell$
neighborhood of each of these nodes, as discussed in the previous point. So
the $4\ell+1$ neighborhood of $z$ in total.

  * •

For loop in Line 7: The path $P$ has length at most $2\ell$, since otherwise
$z_{1},z_{2}$ would not be done yet. As discussed in the previous point, nodes
in $Z$ know whether or not they are done after $4\ell+1$ rounds. As a result
nodes in $P$ will know if they are between two nodes that are done after at
most $6\ell+1$ rounds.

∎

Input: $\ell,Z,f_{\Pi,\infty}$

1 $p=\frac{1}{2\ell}$

2 for  _every node $u\in N\setminus Z$_ do

3 if  _$u$ has a neighbor in $Z$ at distance $\leq\ell$_ then

4 set $u$ to be inactive

5

6 else

7 $u$ becomes a candidate with probability $p=\frac{1}{2\ell}$
$\triangleright$ so $u$ is active

8

9 if  _$u$ is the only candidate in its $\ell$ neighborhood_ then

10 $u$ joins $Z$

11

12

13for  _every node $z\in Z$_ do

14 if  _there are two other nodes $z_{1},z_{2}\in Z$ at distance at most
$2\ell+1$_ then

15 $P_{1}\leftarrow$ the path between $z_{1}$ and $z$

16 $P_{2}\leftarrow$ the path between $z_{2}$ and $z$

17 apply $f_{\Pi,\infty}$ to $P_{1}$ and $P_{2}$

18 $z$ now has only incoming edges and can compute its maximal class $B_{z}$
and assign labels to all incoming edges

19 mark $z$ as done

20

21

22for  _every path $P$ between two nodes $z_{1},z_{2}\in Z$ that are done_ do

23 Each node $u\in P$ was already assigned a label set in Line 7

24 Use the labelsets that were assigned by $z_{1},z_{2}$ to chose labels for
all edges in $P$

25 Propagate the choices of labels to all incoming edges of nodes in $P$

26 mark all nodes in $P$ as done

27

Algorithm 7 Elect Maximums

######  Lemma 43.

At the end of the execution of _randomized Compress_ Algorithm 6 the nodes in
$N\setminus Z$ form paths of length in $[\ell,2\ell]$ with high probability.

###### Proof.

Whenever we add a node $u$ into $Z$, then this node must be active and
therefore at distance at least $\ell+1$ from any node already in $Z$.
Furthermore nodes may only join $Z$, if no other node at distance $\ell$ is
joining the set at the same time, that is are not also a candidate. As a
result no two nodes at distance less than $\ell+1$ will join $Z$. So paths
between two nodes in $Z$ have length at least $\ell$. Now for a path to be
longer than $2\ell$, there must be at least one node $u$ in the middle that
has distance $>\ell$ from all nodes in $Z$. But then this means, that $u$ was
active in all of the executions of _Elect Maximum_. So we get:

$\displaystyle Pr[u\notin Z\mid\forall z\in Z:dist(u,z)>\ell]$
$\displaystyle=\prod_{1\leq i\leq 4\ell c\ln n}Pr[u\text{ doesn't join $Z$ in
iteration }i\mid u\text{ is active}]$

Then by Lemma 41 the probability that $u$ did not join $Z$ itself in one of
the iterations is $1-\frac{1}{8\ell}$. So we get:

$Pr[u\notin Z\mid\forall z\in Z:dist(u,z)>\ell]\leq(1-\frac{1}{8\ell})^{8\ell
c\ln n}\leq e^{-\frac{8\ell c\ln n}{8\ell}}=e^{-c\ln n}=\frac{1}{n^{c}}$

Where we used that $(1+x)\leq e^{x}$. The statement now follows by a simple
union bound over all nodes. ∎

Now we can use this to prove that we correctly solve the compress problem.

######  Lemma 44.

The algorithm _randomized Compress_ Algorithm 6 computes a valid solution to
the Compress Problem.

###### Proof.

We first take care of the initial case in which $v_{l}=v_{r}$, but then
$v_{l}$ is between the two compress paths $P_{l}$ and $P_{r}$. So $v_{l}$ has
only incoming edges and is therefore a local maximum. We therefore extend the
existing partial $(\gamma,\ell,i)$-decomposition with $P_{l}\subset
V^{C}_{i-1}$, $P_{r}\subset V^{C}_{i-1}$and $v_{l}\in V^{R}_{i,1}$.
In the second case we compute the subset $Z$, such that paths between nodes of
$Z$ have length in $[\ell,2\ell]$ by Lemma 43. We again extend the partial
$(\gamma,\ell,i)$-decomposition, by putting all of the nodes in $Z$ into layer
$V^{R}_{i,1}$ and the nodes in the paths in layer $V^{C}_{i-1}$.
In both cases we produce a valid $(\gamma,\ell,i)$-decomposition, analogous to
the argumentation of Lemma 15. We then pick labels according to the labelsets
given by the feasible function and maximal classes. We output the correct
labelsets for both $P_{l},P_{r}$ and $e_{l},e_{r}$. Furthermore the labels
that are chosen in $N$ are due to a valid $(\gamma,\ell,i)$-decomposition and
using the feasible function $f_{\Pi,\infty}$, so correctness follows from the
results of [19], for details see Section 4.2. ∎

Finally, we prove that nodes are done and can terminate after a constant
number of rounds in expectation, thus proving constant node averaged
complexity for all LCL’s with worst case complexity $O(\log n)$ by Lemma 40.
We first start with the probability that nodes are _done_ , meaning they have
picked labels for their incident edges and can terminate.

######  Lemma 45.

Any node $z$ that was initially in $Z$, or that joined $Z$ after the Loop in
Line 7, is marked as _done_ with constant probability.

###### Proof.

Consider the $2\ell+1$ neighborhood of $z$ and let
$A=(v^{left}_{2\ell+1},\ldots,v^{left}_{1},z,v^{right}_{1},\ldots,v^{right}_{2\ell+1})$
be the path around $z$. The distinction between left and right is done
arbitrarily based on the two outgoing edges of $z$ and just for the analysis.
Because of Lemma 43 the nodes at distance at most $\ell$ of $z$ cannot be in
$Z$ themselves, so
$v^{left}_{\ell},\ldots,v^{left}_{1},v^{right}_{1},\ldots,v^{right}_{\ell}$
are not in $Z$ and are also not active during this execution of _Elect
Maximums_. We will show that on both sides there is a constant probability of
a node being in $Z$ and then argue that both sides are independent of one
another. So lets for now just focus on the left side. If any of the nodes in
$v^{left}_{2\ell+1},\ldots,v^{left}_{\ell+1}$(respectively
$v^{right}_{\ell+1},\ldots,v^{right}_{2\ell+1}$) were in $Z$ initially, then
we are done. If this is not the case, than this means that
$v^{left}_{\ell+1}$(respectively $v^{right}_{\ell+1}$) was active at the
beginning of the execution. So by Lemma 41 $v^{left}_{\ell+1}$ joined $Z$ with
probability $\frac{1}{8\ell}$101010In fact even with probability
$\frac{1}{4\ell}$, by redoing the analysis of Lemma 41 but conditioned on
$v^{left}_{1},v^{right}_{1},\ldots,v^{right}_{\ell}$ not joining. Notice also,
that this is independent of the right side, as $v^{left}_{\ell+1}$ and
$v^{right}_{\ell+1}$ are at least $2\ell$ apart and nodes decide to join $Z$
only considering their $2\ell$ neighborhood. So we get:

$Pr[z\text{ is done}\mid z\in Z]\geq Pr[v^{left}_{\ell+1}\text{ joins }Z]\cdot
Pr[v^{right}_{\ell+1}\text{ joins }Z]\geq\frac{1}{(8\ell)^{2}}$

We also note that more active nodes in $A$ would only result in a higher
probability. ∎

Now we use this to prove that also the nodes which do not join $Z$ are done
quickly and that as a result nodes terminate after a constant number of
iterations in expectation. This together with Lemma 40 proves Theorem 2.

######  Lemma 46.

In every execution of _Elect Maximums_ every node has a constant probability
of being done. Furthermore every node can terminate after a constant number of
rounds in expectation when executing _randomized Compress_ Algorithm 6.

###### Proof.

There are three different possibilities for every node $v$:

  * •

Node $v$ is active: Then by Lemmas 41 and 45 we get:

$\displaystyle Pr[v\text{ is done}]\geq Pr[v\text{ joins }Z]Pr[v\text{ is
done}\mid v\in Z]\geq\frac{1}{(8\ell)^{3}}$

  * •

Node $v$ is already in $Z$: Then by Lemma 45 we have:

$\displaystyle Pr[v\text{ is done}]=Pr[v\text{ is done}\mid v\in
Z]\geq\frac{1}{(8\ell)^{2}}$

  * •

Node $v$ is inactive: Then $v$ can only be done, if it is between two nodes
$z_{1},z_{2}\in Z$ that are themselves done. Since $v$ is inactive, this means
that there is at least one node $z_{r}$ at distance less than $\ell$ that is
in $Z$. Consider the $2\ell$ neighborhood of $v$ and let
$A=(v^{left}_{2\ell},\ldots,v^{left}_{1},v,v^{right}_{1},\ldots,v^{right}_{2\ell})$
be the path around $v$. The distinction between left and right is done
arbitrarily based on the two outgoing edges of $v$ and just for the analysis.
W.lo.g. let $z_{r}$ be among $v^{right}_{1},\ldots,v^{right}_{\ell}$. We
denote by $1\leq d:=\text{dist}(v,z_{r})<\ell$ and refer the reader to Fig. 12
for an illustration of the scenario. As a result $v^{left}_{1},\ldots
v^{left}_{\ell-d-1}$ must also be inactive. So we consider two cases for the
nodes $v^{left}_{2\ell-d},\ldots,v^{left}_{\ell-d}$.

    * –

Case 1:
$Z\cap\\{v^{left}_{2\ell-d},\ldots,v^{left}_{\ell-d}\\}\neq\emptyset$:
Then let $z_{l}\in Z\cap\\{v^{left}_{2\ell-d},\ldots,v^{left}_{\ell-d}\\}$ be
the unique node in the set, because $Z$ is the subset of a ruling set
according to Lemma 43. Then the probability that $v$ is done is at least:

$\displaystyle Pr[v\text{ is done}]\geq Pr[z_{l}\text{ is done}\mid v\in
Z]Pr[z_{r}\text{ is done}\mid v\in Z]\geq\frac{1}{(8\ell)^{4}}$

    * –

Case 2:  $Z\cap\\{v^{left}_{2\ell-d},\ldots,v^{left}_{\ell-d}\\}=\emptyset$:
Then at least $v^{left}_{\ell-d}$ must be active and therefore the probability
that $v$ is done is at least:

$\displaystyle Pr[v\text{ is done}]\geq Pr[v^{left}_{\ell-d}\text{ joins
}Z]Pr[v^{left}_{\ell-d}\text{ is done}\mid v\in Z]Pr[z_{r}\text{ is done}\mid
v\in Z]\geq\frac{1}{(8\ell)^{5}}$

Figure 12: Illustrating the third case in the proof of Lemma 46.

So even in the worst case of the above three scenarios the probability is at
least $\frac{1}{(8\ell)^{5}}$ as claimed.
For the furthermore part, we observe that the number of executions until a
node is done is geometrically distributed. Let $p$ be the actual probability
that a node $v$ is done after the execution of _Elect Maximums_. Then the
random variable $X_{v}$ of how many iterations of _Elect Maximums_ it takes
for a node to terminate is geometrically distributed. As a result
$\mathbb{E}[X_{v}]=\frac{1}{p}\leq(8\ell)^{5}$. This together with Lemma 42
proves the claim. ∎

##  7 Improved Algorithms in the Polynomial Regime

In this section we show that, for infinitely many LCL problems with polynomial
worst-case complexity, we can improve their node-averaged complexity. More
precisely, in this section we show that, for a class of problems with worst-
case complexity $\Theta(n^{1/k})$, we can provide an algorithm with node-
averaged complexity $O(n^{1/(2^{k}-1)})$. As we show in Section 8, this
complexity is almost tight, since for all problems with worst-case complexity
$\Theta(n^{1/k})$ we can show a lower bound of
$\widetilde{\Omega}(n^{1/(2^{k}-1)})$.

###  7.1 The Hierarchical $2\frac{1}{2}$-Coloring Problems

We now define a class of problems, already presented in [19], called
hierarchical $2\frac{1}{2}$-coloring, that is parametrized by an integer
$k\in\mathbb{Z}^{+}$. It has been shown in [19] that the problem with
parameter $k$ has worst-case complexity $\Theta(n^{1/xk})$. We now give a
formal definition of this class of problems and then we provide some
intuition.

The set of input labels is $\Sigma_{\mathrm{in}}=\emptyset$. The set of output
labels contains four possible labels, that is,
$\Sigma_{\mathrm{out}}=\\{W,B,E,D\\}$, and these labels stand for _white_ ,
_black_ , _exempt_ , and _decline_. Each node has a level in
$\\{1,\ldots,k+1\\}$, that can be computed in constant time, and the
constraints of the nodes depend on the level that they have. The level of a
node is computed as follows.

  1. 1.

Let $i\leftarrow 1$.

  2. 2.

Let $V_{i}$ be the set of nodes of degree at most $2$ in the remaining tree.
Nodes in $V_{i}$ are of level $i$. Nodes in $V_{i}$ are removed from the tree.

  3. 3.

Let $i\leftarrow i+1$. If $i\leq k$, continue from step 2.

  4. 4.

Remaining nodes are of level $k+1$.

Each node must output a single label in $\Sigma_{\mathrm{out}}$, and based on
their level, they must satisfy the following local constraints.

  * •

No node of level $1$ can be labeled $E$.

  * •

All nodes of level $k+1$ must be labeled $E$.

  * •

Any node of level $2\leq i\leq k$ is labeled $E$ iff it is adjacent to a lower
level node labeled $W$, $B$, or $E$.

  * •

Any node of level $1\leq i\leq k$ that is labeled $W$ (resp. $B$) has no
neighbors of level $i$ labeled $B$ (resp. $W$) or $D$. In other words, $W$ and
$B$ are colors, and nodes of the same color cannot be neighbors in the same
level.

  * •

Nodes of level $k$ cannot be labeled $D$.

This problem can be expressed as a standard LCL (a type of LCLs defined in
Appendix C) by setting the checkability radius $r$ to be $O(k)$, since in
$O(k)$ rounds a node can determine its level and hence which constraints
apply.

#### Some intuition on these problems.

In order to have a bit of intuition on this class of problems, let us consider
the case when $k=2$, for which the worst-case complexity is
$\Theta(\sqrt{n})$. Let us focus on nodes of levels $1$ and $2$ (note that
these are the only nodes that matter, since nodes of level $3$ will blindly
output $E$). Notice that, by the definition of the level of a node, nodes of
the same level form paths. Let $Q$ be a path of level-$1$ nodes. By the
definition of the LCL problems described above, $Q$ must either be $2$-colored
by using the labels $W$ and $B$, or all nodes in $Q$ must be labeled $D$. Now
consider a path $P$ of level-$2$ nodes. By the definition of the LCL problems,
a node in $P$ must be labeled $E$ if and only if it has a level-$1$ neighbor
labeled with $W$ or $B$. On the other hand, the subpaths of $P$ induced by
nodes having a level-$1$ neighbor labeled $D$ must be $2$-colored by using the
labels $W$ and $B$.

On the lower bound side, a worst-case instance for this LCL with parameter
$k=2$ consists of a path $P$ of length $\Theta(\sqrt{n})$, where to each node
$v_{j}$ of $P$ is attached a path $Q_{j}$ of length $\Theta(\sqrt{n})$. If an
algorithm performs a $2$-coloring of any of the $Q_{j}$ paths, then it needs
to spend $\Omega(\sqrt{n})$ rounds. Otherwise, if none of the $Q_{j}$ paths
gets $2$-colored, then any correct algorithm must $2$-color $P$, spending
$\Omega(\sqrt{n})$ rounds.

On the upper bound side, this LCL with parameter $k=2$ can be solved in
$O(\sqrt{n})$ rounds in the following way. First, level-$1$ nodes spend
$O(\sqrt{n})$ rounds to check if the path that they are in has length
$O(\sqrt{n})$: if yes, then the path gets $2$-colored with labels $W$ and $B$;
if no, the path gets labeled with $D$. If a level-$2$ node has a level-$1$
neighbor that is colored (i.e., it is labeled $W$ or $B$), then it outputs
$E$. Finally, it is possible to prove that the subpaths induced by nodes of
level $2$ that have a level-$1$ neighbor labeled $D$ must be of length
$O(\sqrt{n})$, hence these subpaths can be $2$-colored in $O(\sqrt{n})$
rounds.

###  7.2 Better Node-Averaged Complexity

We now show that, for the class of LCL problems described in Section 7.1, we
can obtain a better node-averaged complexity. The algorithm is similar to the
one presented in [16] for the worst-case complexity, but it is modified to
obtain a better node-averaged complexity (in Section 8 we show that this
algorithm is tight up to a $\log n$ factor).

######  Theorem 47.

The node-averaged complexity of the hierarchical $2\frac{1}{2}$-coloring
problem with parameter $k$ is $O(n^{1/(2^{k}-1)})$.

###### Proof.

At first, all nodes spend $O(1)$ rounds to compute their level. Nodes of level
$k+1$ output $E$. Then, the algorithm proceeds in phases, for $i$ in
$1,\ldots,k$. In phase $i$, all nodes of level $i$ get a label, and hence let
us assume that all nodes of levels $1,\ldots,i-1$ already have a label, and
let us focus on level-$i$ nodes.

Consider a node $v$ of level $i$. Node $v$ proceeds as follows. If $v$ has a
neighbor from lower levels that is labeled $W$ or $B$ then $v$ outputs $E$.
Otherwise, $v$ spends $t_{i}=c\cdot\gamma_{i}$ rounds to check the length of
the path containing $v$ induced by nodes of level $i$, for some constant $c$
to be fixed later, and $\gamma_{i}=n^{2^{i-1}/(2^{k}-1)}$. If this length is
strictly larger than $t_{i}$, then $v$ outputs $D$. Otherwise, all nodes of
the path are able to see the whole path, and hence they can output a
consistent $2$-coloring by using the labels $W$ and $B$.

The above algorithm correctly solves the problem if we assume that no nodes in
level $k$ output $D$. In the following we show that indeed nodes of level $k$
do not output $D$, hence showing the correctness of the algorithm, and then we
prove a bound on the node-averaged complexity.

In order to do so, we first prove a useful statement. Let $S$ be the set of
nodes of level $i$ that do not directly output $E$ at the beginning of phase
$i$. It is possible to assign each node of level $j<i$ to exactly one node in
$S$ such that to each node in $S$ are assigned
$\Omega(n^{(2^{i-1}-1)/(2^{k}-1)})$ unique nodes of lower layers. Let $v$ be a
node in $S$. Since $v\in S$, it means that $v$ is connected to a path $P$ of
nodes of level $i-1$ of length strictly larger than $t_{i-1}$, and hence all
nodes in $P$ are labeled $D$. Since, by the definition of the levels, $P$ has
at most $2$ nodes of higher levels connected to it, then we can charge
$t_{i-1}/2$ unique nodes to $v$. By repeating this reasoning inductively, we
obtain that for each node of layer $i$ that does not directly output $E$, we
can assign at least the following amount of nodes:

$\prod_{j=1}^{i-1}t_{j}/2=\Omega\left(\prod_{j=1}^{i-1}\gamma_{j}\right)=\Omega(n^{\sum_{j=1}^{i-1}2^{j-1}/(2^{k}-1)})=\Omega(n^{(2^{i-1}-1)/(2^{k}-1)}).$

Hence, the number of nodes that participate in phase $i$ is at most
$O(n^{1-(2^{i-1}-1)/(2^{k}-1)})=O(n^{(2^{k}-2^{i-1})/(2^{k}-1)})$. This
implies that in phase $k$ the number of participating nodes is at most
$O(n^{(2^{k}-2^{k-1})/(2^{k}-1)})=O(n^{2^{k-1}/(2^{k}-1)})=O(\gamma_{k})$,
where the hidden constant is inversely proportional to $c$. Hence, by picking
$c$ large enough, we get that in $t_{k}$ rounds nodes of level $k$ see the
whole path and thus no node of level $k$ outputs $D$, proving the correctness
of the algorithm.

The total time spent during phase $i$ is bounded by

$O(\gamma_{i}\cdot n^{1-(2^{i-1}-1)/(2^{k}-1)})=O(n^{2^{i-1}/(2^{k}-1)}\cdot
n^{1-(2^{i-1}-1)/(2^{k}-1)})=O(n^{1+1/(2^{k}-1)}).$

Therefore, the average time spent in phase $i$ is bounded by
$O(n^{1/(2^{k}-1)})$. Since this is done for $i\in\\{1,\ldots,k\\}$, and since
$k=O(1)$, then the claim on the node-averaged complexity follows. ∎

##  8 Lower Bounds in the Polynomial Regime

In this section we show that any LCL problem that requires polynomial time for
worst-case complexity requires polynomial time also for node-averaged
complexity. More precisely, we prove the following theorem.

######  Theorem 48.

Let $\Pi$ be an LCL problem with worst-case complexity $\Omega(n^{1/k})$ in
the $\mathsf{LOCAL}$ model. The randomized node-averaged complexity of $\Pi$
in the $\mathsf{LOCAL}$ model is $\Omega(n^{1/(2^{k}-1)}/\log n)$, and the
deterministic node-averaged complexity of $\Pi$ in the $\mathsf{LOCAL}$ model
is $\Omega(n^{1/(2^{k}-1)})$.

In order to prove this theorem, we proceed as follows (throughout this section
we will use notions presented in Section 4.2). It is known by [16] that if an
LCL problem $\Pi$ has worst-case complexity $o(n^{1/k})$, then it can actually
be solved in $O(n^{1/(k+1)})$ deterministic rounds. This statement is proved
by showing that it is possible to use an algorithm (possibly randomized)
running in $o(n^{1/k})$ rounds to construct a good function $f_{\Pi,k+1}$
(that is, a function $f_{\Pi,k+1}$ that, if used, never creates empty
classes), implying (as shown in Section 4.2) the existence of a deterministic
algorithm that solves $\Pi$ and has worst-case complexity $O(n^{1/(k+1)})$. In
this section we show that it is possible to construct a good function
$f_{\Pi,k+1}$ by starting from an algorithm $\mathcal{A}$ with randomized
node-averaged complexity $o(n^{1/(2^{k}-1)}/\log n)$ or deterministic node-
averaged complexity $o(n^{1/(2^{k}-1)})$. By Section 4.2, this implies that if
there exists an algorithm with $o(n^{1/(2^{k}-1)}/\log n)$ randomized node-
averaged complexity or with $o(n^{1/(2^{k}-1)})$ deterministic node-averaged
complexity, then there exists an algorithm with deterministic worst-case
complexity $O(n^{1/(k+1)})$. This shows that any LCL with worst-case
complexity $\Omega(n^{1/k})$ has node-averaged complexity at least
$\Omega(n^{1/(2^{k}-1)}/\log n)$ randomized and $\Omega(n^{1/(2^{k}-1)})$
deterministic. While we will use some ideas already presented in [16],
handling an algorithm with only guarantees on its node-averaged complexity
arises many (new) issues that we need to tackle.

Our statement will be proved even for the case in which the randomized
algorithm $\mathcal{A}$ satisfies the weakest possible assumptions, i.e., the
assumptions are so relaxed that they are satisfied by any deterministic
algorithm, any randomized Las Vegas algorithm, and any randomized Monte Carlo
algorithm. The assumptions are the following.

  * •

We assume that $\mathcal{A}$ is a randomized algorithm that is only required
to work when the unique IDs of nodes are assigned at random, among all
possible valid assignments.

  * •

We assume that $\mathcal{A}$ is an algorithm that fails with probability at
most $1/n^{c}$ for any chosen constant $c\geq 1$.

  * •

We assume that the bound on the node-averaged complexity of $\mathcal{A}$
holds with probability at least $1-1/n^{c}$ for any chosen constant $c\geq 1$.

However, in the following, we will assume that the bound on the node-averaged
complexity of $\mathcal{A}$ always holds. In fact, observe that we can always
convert an algorithm with node-averaged complexity $T$ that holds with
probability at least $1-1/n^{c}$ into an algorithm with node-averaged
complexity $O(T)$ that holds always, since, even for $c=1$, we can safely
assume that when the bound does not hold (that happens with probability at
most $1/n$), the runtime is anyways bounded by $n$ (since everything can be
solved in $n$ rounds in the LOCAL model).

###  8.1 Good Functions

We now describe how, in [19, 16], it is determined whether a good function
exists. In the following, we call _solver_ the algorithm for solving an LCL
given a decomposition, presented in Section 4.2.

There are two main ingredients that are used in [19, 16]. One is that there
are a finite amount of possible functions, and this is true since the classes
of Definition 5 have finite size, and since there is a finite amount of ways
to map maximal classes into independent ones. The other is that, given a
function, there is a centralized algorithm that checks whether the function is
good. The key question is how to test whether a function is good, and, on a
high level, this is done by constructing all possible label-sets that could
possibly appear while running the solver, which depend on the tested function.
Crucially, this is a finite amount, and there is a recursive procedure that
can generate them.

#### What actually determines the complexity of a problem.

We now provide some more intuition about the function $f_{\Pi,k}$, and about
how the existence of this function is related with the worst-case complexity
of a problem. In [19, 16] it is shown how to determine whether a good function
exists (that is, a function that never creates empty classes), and if it
exists, how to construct it. Also, it is shown that:

  * •

If a problem is solvable in $O(\log n)$ rounds, then a good function
$f_{\Pi,\infty}$ exists.

  * •

If a problem is solvable in $o(n^{1/k})$, then a good function $f_{\Pi,k+1}$
exists.

This implies that, if a problem is solvable in $O(\log n)$ rounds, then we can
automatically find a good function that makes the solver work and solve the
problem in $O(\log n)$ rounds, and if a problem is solvable in $o(n^{1/k})$,
then we can automatically find a good function that makes the solver work and
solve the problem in $O(n^{1/(k+1)})$ rounds. Also, given a problem $\Pi$, it
is possible to compute what is the optimal target complexity, that is, we can
determine whether the problem can be solved in $O(\log n)$ rounds, and if the
answer is negative we can determine the best integer $k$ for which the problem
can be solved in $O(n^{1/k})$ rounds.

The intuition about what determines the existence of a good function
$f_{\Pi,k}$ is the following. Compress paths are something that is difficult
to handle, because they require to restrict the label-sets that we propagate
up in order to make them “independent”. The number of compress layers that we
can recursively handle is what determines the complexity of a problem.

  * •

If we can handle an arbitrary amount of compress layers, then we can construct
a good function $f_{\Pi,\infty}$, and hence the problem can be solved in
$O(\log n)$ rounds.

  * •

If we can handle only a constant amount of compress layers, say $k-1$, then a
good function $f_{\Pi,k}$ exists, but $f_{\Pi,k+1}$ does not, and then the
complexity of the problem is $\Theta(n^{1/k})$.

#### Testing procedure.

We now present an algorithm that tests whether a function $f_{\Pi,k}$ is good.
We call this algorithm _testing procedure_. The procedure depends not only on
the function to be tested, but also on a parameter $\ell$ that, in [19, 16],
is shown that it can be determined solely as a function of $\Pi$. We observe
that this algorithm is well-defined also when $k=\infty$, and in fact this
algorithm can be used also to determine whether a problem can be solved with
$O(\log n)$ worst-case complexity. The idea of the testing procedure is to
keep track of all label-sets that one could possibly obtain while running the
solver. For each of these label-sets, we also keep track of a subtree (where
nodes are also marked with the layers of a decomposition) where, if we run the
solver by using the function that we are testing, we would obtain an edge with
such a label-set. While this is not necessary for _testing_ a function, we
will use these trees later for _constructing_ a function given an algorithm.
We now formally describe the testing procedure and later we will give more
intuition on it.

  1. 1.

Initialize $S$ with all the possible values of the label-set $g(v)$ of $v$ (as
defined in Definition 6) that could be obtained when $v$ is a leaf. Note that
the possible values are a finite amount that only depends on the amount of
input labels of $\Pi$. Initialize $\mathcal{R}_{1}$ by inserting one pair
$((\tilde{T},u),L)$ for each element $L$ in $S$, where $\tilde{T}$ is a tree
composed of $2$ nodes $\\{u,v\\}$ and $1$ edge $\\{u,v\\}$, and $L=g(v)$. Node
$v$ is marked as a rake node of layer $1$, while $u$ is marked as a temporary
node.

  2. 2.

For $i=1,\ldots,k$ do the following. If, at any step, an empty label-set is
obtained, then the tested function is not good.

    1. (a)

Do the following in all possible ways. Consider $x$ arbitrary elements
$((\tilde{T}_{j},v_{j}),L_{j})$ of $\mathcal{R}_{i}$, where $1\leq j\leq x$
and $1\leq x\leq\Delta$. Construct the tree $T$ as the union of all trees
$\tilde{T}_{j}$, where all the nodes $v_{j}$ (note that each node $v_{j}$ has
degree $1$) are identified as a single node, call it $v$, which, after this
process, has degree $x$ in $T$. Let $F_{\mathrm{incoming}}$ be the set of
edges connected to $v$, and let $\mathcal{L}_{\mathrm{incoming}}$ be the
label-set assignment given by the sets $L_{j}$. The node $v$ is marked as a
rake node of layer $i$. If $v$ has an empty maximal class w.r.t.
$F_{\mathrm{incoming}}$, $F_{\mathrm{outgoing}}=\\{\\}$, and
$\mathcal{L}_{\mathrm{incoming}}$, then the tested function is not good.

    2. (b)

Do the following in all possible ways. Consider $x$ arbitrary elements
$((\tilde{T}_{j},v_{j}),L_{j})$ of $\mathcal{R}_{i}$, where $1\leq j\leq x$
and $1\leq x\leq\Delta-1$. Construct the tree $T$ as the union of all trees
$\tilde{T}_{j}$, where all the nodes $v_{j}$ are identified as a single node,
call it $v$. Attach an additional neighbor $u$ to $v$. Let
$F_{\mathrm{outgoing}}=\\{\\{u,v\\}\\}$. Let $F_{\mathrm{incoming}}$ be the
set of edges connected to $v$, excluding $\\{u,v\\}$, and let
$\mathcal{L}_{\mathrm{incoming}}$ be the label-set assignment given by the
sets $L_{j}$. The node $v$ is marked as a rake node of layer $i$, while $u$ is
marked as a temporary node. Let $L=g(v)$ (as defined in Definition 6). If $L$
is empty, then the function is not good. Add $((T,u),L)$ to $\mathcal{R}_{i}$
if no pair with second element $L$ is already present.

    3. (c)

Repeat the previous two step until nothing new is added to $\mathcal{R}_{i}$.
This must happen, since there are a finite amount of possible label-sets.

    4. (d)

If $i=k$, stop.

    5. (e)

Initialize $\mathcal{C}_{i}=\emptyset$.

    6. (f)

Do the following in all possible ways. Construct a graph starting from a path
$H$ of length between $\ell$ and $2\ell$ where we connect nodes of degree $1$
to the nodes of $H$ satisfying: (i) all nodes in $H$ have degree at most
$\Delta$; (ii) the two endpoints of $H$ have an outgoing edge that connects
respectively to nodes $u_{1}$ and $u_{2}$ that are nodes of degree $1$; (iii)
all the other edges connecting degree-$1$ nodes to the nodes of $H$ are
incoming for $H$. Next, replace each incoming edge $e$ and the node of degree
$1$ connected to it with a tree $\tilde{T}$ of a pair $((\tilde{T},u),L)$ in
$\mathcal{R}_{i}$, by identifying $u$ with the node of the path connected to
$e$. Different trees can be used for different edges. The nodes $u_{1}$ and
$u_{2}$ are marked as temporary nodes, while the nodes of the path are marked
as compress nodes of layer $i$. Use the function as described in Definition 6
to compute the label-sets $L_{1}$ and $L_{2}$ of the two endpoints. If $L_{1}$
or $L_{2}$ is empty, then the function is not good. Otherwise, add the pair
$((H,u_{1}),L_{1})$ (resp. $((H,u_{2}),L_{2})$) to $\mathcal{C}_{i}$ if no
pair with second element $L_{1}$ (resp. $L_{2}$) is already present. The
_representative tree_ of
$P=(H,F_{\mathrm{incoming}},F_{\mathrm{outgoing}},\mathcal{L}_{\mathrm{incoming}})$
is defined as $r(P)=T$.

    7. (g)

Set $\mathcal{R}_{i+1}=\mathcal{R}_{i}\cup\mathcal{C}_{i}$. If
$\mathcal{R}_{i+1}=\mathcal{R}_{i}$, stop.

On a high level, the testing procedure does the following. Item 1 computes all
possible label-sets that we can get from leaf nodes; leaf nodes are then
marked as rake nodes. Item 2a considers all possible ways to assign a label-
set to all the incident edges of a node $v$, and checks, for each case, if
there is a way for $v$ to label its incident edges (with a label from the
provided label-sets) such that the constraints of node $v$ are satisfied. Node
$v$ is marked as a rake node. This case corresponds to a rake node with no
neighbors in higher layers. Item 2b considers all possible ways to assign a
label-set to all but one incident edge of a node $v$; let $e$ be the edge that
does not have a label-set assigned. Then, the label-set of $e$ is computed as
a function of all the label-sets of the other edges incident to $v$, and then
$v$ is marked as a rake node. This case corresponds to a rake node with one
neighbor in higher layers. In Item 2c the last two steps are repeated until no
new label-sets are obtained. In other words, items 2a, 2b, and 2c generate all
possible label-sets that we can get by performing only rakes, that is, before
performing the first compress. Finally, Item 2f considers all possible label-
sets that we can obtain for the endpoints of a compress path. By repeating
recursively the procedure interleaving between rake and compress nodes, and by
checking at any point that we do not get empty classes or empty label-sets, we
can test whether a function is good or not. An example of a tree generated by
this procedure is shown in Figure 13.

It is possible to prove that the testing procedure generates exactly those
label-sets that could possibly be obtained by running the solver [19, 16].
Hence, if empty classes or empty label-sets are never obtained, then the
function can indeed be used to solve a problem. Observe that all the edges of
a representative tree can be oriented such that: all nodes have at most one
outgoing edge; any directed path contains layers in non-decreasing order (see
Figure 13). While in a generic tree decomposition this may be false, this is
not an issue: the obtained label-sets, in this restricted set of cases, are
still all the possible ones that could be obtained on an arbitrary tree
decomposition.

Figure 13: An example of a tree generated by the testing procedure. Triangles
marked $R_{i}$ correspond to trees of constant size containing only nodes
marked rake of layer $i$. Paths marked $C_{i}$ correspond to nodes marked
compress of layer $i$. At the end of each path, on the side not connected to a
triangle, is connected a temporary node, not shown in the picture. The top
node of the triangle marked $R_{3}$ may be a temporary node.

###  8.2 Some Useful Ingredients

As already discussed, the main goal of this section is to show that it is
possible to construct a good function $f_{\Pi,k+1}$ by starting from an
algorithm $\mathcal{A}$ with randomized node-averaged complexity
$o(n^{1/(2^{k}-1)}/\log n)$ or deterministic node-averaged complexity
$o(n^{1/(2^{k}-1)})$. Before diving into that, we provide some ingredients
that will later be useful.

#### Pumping lemma for trees.

We will use a fundamental ingredient provided in [19], that, informally,
allows us to take a compress path of some class, and make the path longer
while preserving its class.

######  Lemma 49 (Pumping lemma for trees [19]).

Assume we are given an LCL
$\Pi=(\Sigma_{\mathrm{in}},\Sigma_{\mathrm{out}},C_{W},C_{B})$ in the black-
white formalism. Let a _compress path_ be a tuple
$(H,F_{\mathrm{incoming}},F_{\mathrm{outgoing}},\mathcal{L}_{\mathrm{incoming}})$
satisfying the following.

  * •

To each node $v_{i}$ of $H$ are connected $d_{i}$ neighbors,
$u_{i,1},\ldots,u_{i,d_{i}}$. $F_{\mathrm{incoming}}$ is the set of edges
connecting the nodes of $H$ with such neighbors.

  * •

To each edge $e$ of $F_{\mathrm{incoming}}$ is assigned a label-set
$L_{e}\subseteq\Sigma_{\mathrm{out}}$.
$\mathcal{L}_{\mathrm{incoming}}=(L_{e})_{e\in F_{\mathrm{incoming}}}$ is this
assignment.

  * •

To each endpoint of $H$ is connected one additional neighbor.
$F_{\mathrm{outgoing}}$ is the set containing the two edges connecting the
endpoints of $H$ to such neighbors.

Let
$(H,F_{\mathrm{incoming}},F_{\mathrm{outgoing}},\mathcal{L}_{\mathrm{incoming}})$
be a compress path where $H$ has length $x$. Let $w$ be an arbitrary integer
that is at least $x$. There exists a constant $\ell$ such that, if
$x\geq\ell$, then it is possible to construct a compress path
$(H^{\prime},F^{\prime}_{\mathrm{incoming}},F^{\prime}_{\mathrm{outgoing}},\mathcal{L}^{\prime}_{\mathrm{incoming}})$
satisfying the following.

  * •

The length of $H^{\prime}$ is at least $w$ and at most $w+\ell$.

  * •

The maximal class of $H^{\prime}$ w.r.t. $\Pi$,
$F^{\prime}_{\mathrm{incoming}}$, $F^{\prime}_{\mathrm{outgoing}}$, and
$\mathcal{L}^{\prime}_{\mathrm{incoming}}$ is equal to the maximal class of
$H$ w.r.t. $\Pi$, $F_{\mathrm{incoming}}$, $F_{\mathrm{outgoing}}$, and
$\mathcal{L}_{\mathrm{incoming}}$.

  * •

The set of label-sets contained in $\mathcal{L}^{\prime}_{\mathrm{incoming}}$
is equal to the set of label-sets contained in
$\mathcal{L}_{\mathrm{incoming}}$.

#### Pumping trees.

Let $T$ be a tree constructed in the testing procedure. Observe that, in this
tree, the nodes are either marked rake, compress, or temporary, and with a
layer number. We provide a procedure $\mathrm{pump}_{k}(w,T)$ that modifies
$T$ to make all compress paths longer. In particular, all compress paths of
layer $i$ will be of length between $w_{i}$ and $w_{i}+\ell$, where $w_{i}$ is
defined to be $w^{2^{i-1}/(2^{k}-1)}$. The procedure $\mathrm{pump}_{k}(w,T)$
performs the following operation recursively, by starting from compress layer
$i=1$ and going up, and by considering all compress paths present in $T$.

  * •

Let
$(H,F_{\mathrm{incoming}},F_{\mathrm{outgoing}},\mathcal{L}_{\mathrm{incoming}})$
be a compress path induced by a connected component of nodes marked as
compress nodes of layer $i$.

  * •

Apply Lemma 49 with parameter $w_{i}$ and get
$(H^{\prime},F^{\prime}_{\mathrm{incoming}},F^{\prime}_{\mathrm{outgoing}},\mathcal{L}^{\prime}_{\mathrm{incoming}})$.

  * •

Remove all the subtrees that are connected to $H$ via edges in
$F_{\mathrm{incoming}}$.

  * •

Replace $H$ with $H^{\prime}$.

  * •

Let $\\{u,v\\}$ be an edge in $F^{\prime}_{\mathrm{incoming}}$, where $u$ is
the node of $H^{\prime}$. Note that $\\{u,v\\}$ has a label-set assigned
according to $\mathcal{L}^{\prime}_{\mathrm{incoming}}$. For each edge
$\\{u,v\\}$ in $F^{\prime}_{\mathrm{incoming}}$ (where $u$ is the node of
$H^{\prime}$) we attach a copy of one subtree that was connected to $H$
satisfying that the label-set assigned to the edge connecting the subtree to
$H$ is the same as the label-set of the edge $\\{u,v\\}$.

Note that the last operation is possible since the set of the label-set in
$\mathcal{L}^{\prime}_{\mathrm{incoming}}$ is the same as the set of the
label-sets in $\mathcal{L}_{\mathrm{incoming}}$, and hence the label-set of
$\\{u,v\\}$ must be a label-set that occurs in some edge in
$F_{\mathrm{incoming}}$ that connects some subtree to a node of $H$.

######  Lemma 50.

Let $T$ be a representative tree. Let $T^{\prime}=\mathrm{pump}_{k}(w,T)$.
$T^{\prime}$ contains $O(w)$ nodes.

###### Proof.

By construction of representative trees (see Figure 13), the number of nodes
is bounded by
$O(\prod_{i=1}^{k}w_{i})=O(w^{\sum_{i=1}^{k}2^{i-1}/(2^{k}-1)})=O(w)$. ∎

#### Adding nodes.

We now provide a procedure that takes as input a value $n$ and a pumped tree
of at most $n$ nodes containing at least one temporary node, and adds nodes to
the tree in order to achieve that the amount of nodes are exactly $n$. The
procedure $\mathrm{add}(n,T)$ is defined as follows. Let $j$ be the maximum
layer index of temporary nodes in $T$, and let $v$ be an arbitrary temporary
node $v$ of layer $j$. We attach a path to $v$ in such a way that the number
of nodes becomes exactly $n$.

#### Optimal form of an algorithm.

It has been shown in [22] that any algorithm can be normalized in a way that
nodes do not spend useless rounds of computation. While such a result has been
proved on graphs with linearly bounded growth, it can be easily adapted, in
the case of LCLs in the black-white formalism, to be more general.

######  Lemma 51 ([22]).

Let $A$ be an algorithm that solves an LCL problem $\Pi$ with node-averaged
complexity $T$. Then, if a node $v$ runs for $t$ rounds, either there exist at
least $t/2-1$ nodes in the $t/2$-radius neighborhood of $v$ that run for at
least $t/2$ rounds, or $v$ could terminate earlier.

###### Proof Sketch.

Suppose that in the $t$-radius neighborhood of $v$ there are at most $t/2-2$
nodes that run for at least $t/2$ rounds. This means that the connected
component $C$ induced by $v$ and nodes that still have to terminate after
$t/2$ rounds is of size strictly less than $t/2$. Also, in strictly less than
$t$ rounds, $v$ sees the state that all these nodes had at time $t/2$, and of
their neighbors. We show that this implies that $v$ can terminate in strictly
less than $t$ rounds, proving the claim. Since $C$ is surrounded by nodes that
already terminated, then $v$, solely as a function of its state, the state
that the nodes of $C$ had at time $t/2$, and the output of the nodes connected
to $C$, can simulate the execution of $A$ for all nodes of $C$ without
additional communication, and obtain an output for all the nodes in $C$, and
hence $v$ can terminate in strictly less than $t$ rounds. ∎

#### From node-averaged complexity to expected runtime.

In the following, we assume $\mathcal{A}$ to be an algorithm for $\Pi$ that
has been normalized according to Lemma 51. We now show that a stronger notion
of node-averaged complexity must hold for $\mathcal{A}$, namely that the
expected running time of each node is bounded. In the case of randomized
algorithms, the expectation is taken over all possible assignments of random
bits and IDs, while for deterministic algorithms the expectation is taken over
all possible assignments of IDs (if we imagine to run the deterministic
algorithm with an ID assignment chosen uniformly at random among the valid
ones).

######  Lemma 52.

Let $\mathcal{A}$ be an algorithm with node-averaged complexity at most
$w^{1/(2^{k}-1)}/f(n)$, where:

  * •

$w=w(n)$ is in $O(n)$;

  * •

for all $n$ that are at least a large enough constant $n^{\prime}$, $f(n)$ is
at least a large enough constant.

Let $T=\mathrm{add}(n,\mathrm{pump}_{k}(w,T^{\prime}))$, where $T^{\prime}$ is
a representative tree. There exists a constant $c>0$ satisfying the following.
For an arbitrary $i$, let $v$ be an arbitrary node in a compress layer $i$
satisfying that $v$ is at distance at least $c\cdot
w^{2^{i-1}/(2^{k}-1)}/f(n)$ from the endpoints of the compress path.

Assume that $\mathcal{A}$ is run on $T$. Then, the expected running time of
node $v$ is at most $c\cdot w^{2^{i-1}/(2^{k}-1)}/f(n)$.

###### Proof.

Assume, for a contradiction, that there exists a node $v$ in a compress layer
$i$ with expected running time strictly larger than $t=c\cdot
w^{2^{i-1}/(2^{k}-1)}/f(n)$, and that is at distance at least $t$ from the
endpoints. Let $B$ be the $t$-radius neighborhood of $v$. Observe that, by
construction (see Figure 13), this neighborhood contains
$y=O(t\cdot\prod_{j=1}^{i-1}w^{2^{j-1}/(2^{k}-1)})=O(c\cdot
w^{(2^{i}-1)/(2^{k}-1)}/f(n))$ nodes. Moreover, for $n$ large enough, this
neighborhood does not contain all nodes of $T$ ($n^{\prime}$ is set to be the
smallest value of $n$ for which this is true). This implies that we can make
$x=\Omega(n/y)$ copies of $B$ and connect them in such a way that each copy of
$v$ has the same view in the constructed tree $T$ and in $B$. Let $U$ be the
resulting tree. By using Lemma 51, we obtain that, by running $\mathcal{A}$ on
$U$, the average of the expected running times is strictly larger than
$x\cdot(t/2)(t/2-1)/n=\Omega(t^{2}/y)$, that, for some constant
$c^{\prime\prime}$, is at least,

$c^{\prime\prime}\cdot\frac{c^{2}\cdot w^{2^{i}/(2^{k}-1)}/f(n)^{2}}{c\cdot
w^{(2^{i}-1)/(2^{k}-1)}/f(n)}=\frac{c^{\prime\prime}\cdot c}{f(n)}\cdot
w^{(2^{i}-2^{i}+1)/(2^{k}-1)}=c^{\prime\prime}\cdot c\cdot
w^{1/(2^{k}-1)}/f(n).$

This implies that the average running time is strictly larger than
$c^{\prime\prime}\cdot c\cdot w^{1/(2^{k}-1)}/f(n)$. By setting
$c=c^{\prime}/c^{\prime\prime}$, we get a contradiction on the assumption on
the runtime of $\mathcal{A}$. ∎

For randomized algorithms, we will use Lemma 52 for the case $f(n)=\Theta(\log
n)$, for which we get the following corollary.

######  Corollary 53.

Let $\mathcal{A}$ be a randomized algorithm with node-averaged complexity at
most $c^{\prime}\cdot w^{1/(2^{k}-1)}/\log n$, where $w=w(n)$ is in $O(n)$,
and $c^{\prime}$ is a small enough constant. Let
$T=\mathrm{add}(n,\mathrm{pump}_{k}(w,T^{\prime}))$, where $T^{\prime}$ is a
representative tree.

There exists a constant $c>0$ directly proportional to $c^{\prime}$ satisfying
the following. For an arbitrary $i$, let $v$ be an arbitrary node in a
compress layer $i$ satisfying that $v$ is at distance at least $c\cdot
w^{2^{i-1}/(2^{k}-1)}/\log n$ from the endpoints of the compress path.

Assume that $\mathcal{A}$ is run on $T$. Then, the expected running time of
$v$ is at most $c\cdot w^{2^{i-1}/(2^{k}-1)}/\log n$, for all $n\geq
n^{\prime}$ for some constant $n^{\prime}$.

###### Proof.

This corollary follows by setting $f(n):=\log n/c^{\prime}$ in Lemma 52. ∎

As already mentioned, Lemma 52 holds also if $\mathcal{A}$ is a deterministic
algorithm that is run on a random ID assignment. However, by the definition of
deterministic node-averaged complexity, the bound on the node-averaged
complexity must hold for any possible valid ID assignment. Moreover, for
deterministic algorithms, we will use $f(n)=\Theta(1)$. We show the following
corollary.

######  Corollary 54.

Let $\mathcal{A}$ be a deterministic algorithm with node-averaged complexity
at most $c^{\prime}\cdot w^{1/(2^{k}-1)}$, where $w=w(n)$ is in $O(n)$, and
$c^{\prime}$ is a small enough constant. Let
$T=\mathrm{add}(n,\mathrm{pump}_{k}(w,T^{\prime}))$, where $T^{\prime}$ is a
representative tree. Let $\mathcal{X}$ be an arbitrary subset of the possible
ID assignments in $T$.

There exists a constant $c>0$ directly proportional to $c^{\prime}$ satisfying
the following. For an arbitrary $i$, let $v$ be an arbitrary node in a
compress layer $i$ satisfying that $v$ is at distance at least $c\cdot
w^{2^{i-1}/(2^{k}-1)}$ from the endpoints of the compress path. Assume that
there exist at least $n$ ID assignments $X_{1},\ldots,X_{n}$ in $\mathcal{X}$
satisfying the following. Let $I_{i}$ be the set of IDs used by nodes at
distance at most $c\cdot w^{2^{i-1}/(2^{k}-1)}$ from $v$ when using the ID
assignment $X_{i}$. For all $i\neq j$, the sets $I_{i}$ and $I_{j}$ are
disjoint.

Then, there exists an ID assignment from $\mathcal{X}$ satisfying that, by
running $\mathcal{A}$ with such an assignment, the runtime of $v$ is bounded
by $c\cdot w^{2^{i-1}/(2^{k}-1)}$.

###### Proof.

Assume for a contradiction that there are $n$ ID assignments satisfying the
requirements, and for all such assignments, $v$ has runtime strictly larger
than $c\cdot w^{2^{i-1}/(2^{k}-1)}$. Similarly as in the proof of Lemma 52, we
can create an instance where the average runtime of the nodes is too high,
reaching a contradiction. In particular, as in the proof of Lemma 52, we can
construct an instance by copying the neighborhood of $v$ for enough times so
that the average runtime is high. However, differently from the randomized
case, we need to ensure that the constructed instance has unique IDs. By the
assumption on the IDs, we can assign different IDs in each copy. ∎

#### Designated nodes, edges, and neighborhoods.

Let $T^{\prime}$ be a representative tree, and let
$T=\mathrm{add}(n,\mathrm{pump}_{k}(w,T^{\prime}))$. For each compress path
$H$ in $T$, we define the _designated node_ of $H$ to be the white node $v$ in
the middle of the path $H$ (breaking ties arbitrarily). Moreover, we define
the _designated edge_ of the path $H$ to be an arbitrary edge in $H$ that is
incident to $v$.

Let $v$ be a designated node of level $i$. We define the designated
neighborhood of $v$ w.r.t. a constant $\beta$ and a function $g$ as the set
$S$ containing the following nodes. Initialize $S$ with $v$ and all the nodes
at distance at most $w_{i}/(\beta g(n))$ from $v$ in the compress path
containing $v$. Then, start from a node $u$ in $S$ and add to $S$ all its
neighbors $z$ of strictly lower layers. If $z$ is in a compress path of layer
$j$, then also add all the nodes at distance at most $w_{j}/\beta$ from $z$ in
the compress path containing $z$. Repeat this operation until nothing new is
added.

#### Independent executions.

We now prove a statement about randomized algorithms running in
$T(n)=o(w^{1/(2^{k}-1)}/\log n)$, where $w=w(n)$ is in $O(n)$. For this
purpose, we consider the set $\mathcal{S}$ of designated neighborhoods w.r.t.
$g(n)=\log n$ and some constant $\beta$ to be fixed later. More in detail, we
use Corollary 53 to show that, with large enough probability, it holds that
any node of the graph, within its running time, is not able to communicate
with two nodes that are part of different designated neighborhoods in
$\mathcal{S}$.

######  Lemma 55.

Let $\mathcal{A}$ be a randomized algorithm with node-averaged complexity
$o(w^{1/(2^{k}-1)}/\log n)$, where $w=w(n)$ is in $O(n)$. Then, for any
arbitrary constant $c$, with probability at least $1-1/n^{c}$, a node is able
to communicate with the nodes of at most one designated neighborhood in
$\mathcal{S}$.

###### Proof.

Let $P$ be a compress path of layer $i$ and let $v$ be the designated node of
$P$. By construction, $P$ is of length at least $w_{i}$, and $P$ is connected
to a node of a higher layer on at most one side (see Figure 13). Assuming the
higher layer exists, let $u$ be the last node of $P$ on that side. We prove
that there exists a node $z$ in $P$ with the following properties: $z$ lies
between $u$ and $v$; with high probability, $z$ does not see neither $u$ nor
$v$, nor nodes at distance at most $w_{i}/\beta$ from them. Showing the
existence of such a node $z$ would imply the claim, since, by definition, a
designated neighborhood, defined as a function of a designated node of layer
$i$, contains:

  * •

some nodes $V$ that are close to the center of a compress path of layer $i$;

  * •

all nodes that are within some bounded distance of nodes in $V$; by
construction, if these nodes lie on some lower-layer compress path, then they
are close to the beginning of such a path.

Hence, for a node to see two different designated neighborhoods, it must be
able to see, at the same time, both the beginning and the middle of the same
compress path, which is not possible if $z$ exists.

Now, what is left, is to show the existence of node $z$. Let $z$ be the node
at distance $w_{i}/4$ from $v$ that lies in the path connecting $u$ and $v$.
Let $P^{\prime}$ be the path containing $z$ induced by nodes at distance
strictly larger than $w_{i}/\beta$ from both $v$ and $u$. Assume $\beta\geq
8$, we get that $P^{\prime}$ has length at least $w_{i}/4$. Consider the
subpath $P^{\prime\prime}$ of $P^{\prime}$ that lies between $z$ and $u$,
which has length at least $w_{i}/8$. We prove that in $P^{\prime\prime}$, with
high probability, there is a node that terminates in a runtime that is
strictly less than half the length of $P^{\prime\prime}$, implying that $z$
cannot see $u$. The same proof holds for the path between $z$ and $v$.

We can split $P^{\prime\prime}$ into $\delta\log n$ disjoint subpaths of
length at least $w_{i}/(16\delta\log n)$, for any chosen constant $\delta$.
For each subpath $P_{i}$, let $v_{i}$ be the central node of the path,
breaking ties arbitrarily.

By applying Corollary 53, we get that the expected runtime of each node
$v_{i}$ is at most $t=w^{2^{i-1}/(2^{k}-1)}/(\alpha\log n)$, for any chosen
constant $\alpha$. The subpaths are of length at least

$w_{i}/(16\delta\log n)=w^{2^{i-1}/(2^{k}-1)}/(16\delta\log n).$

Hence, we can choose $\alpha$ large enough, as a function of $\delta$, so that
the expected runtime of the nodes $v_{i}$ is less than $1/4$ of the length of
$P_{i}$. Observe that, by the Markov inequality, the probability that a node
$v_{i}$ runs for more than $1/2$ of the length of $P_{i}$ is at most $1/2$,
and also observe that these events are independent for each $v_{i}$. Finally,
note that, in order to be possible for $z$ to communicate with $u$, it must
hold that all nodes $v_{i}$ run for strictly more than $1/2$ of the length of
$P_{i}$, and this happens with probability at most $1/2^{\delta\log
n}=1/n^{\delta}$. ∎

######  Lemma 56.

Let $\mathcal{A}$ be a randomized algorithm with node-averaged complexity
$o(w^{1/(2^{k}-1)}/\log n)$ and failure probability at most $1/n^{c}$, where
$w=w(n)$ is in $O(n)$. For each designated neighborhood $S\in\mathcal{S}$, let
$E^{1}_{S}$ be the event satisfying that, by running $\mathcal{A}$ on the
designated node $v$ in $S$, $v$ does not communicate with any node outside
$S$. Note that $E^{1}_{S}$ solely depends on the random bits (including random
IDs) assigned to the nodes of $S$. Moreover, let $E^{2}_{S}$ be an event that
solely depends on the random bits assigned to the nodes of $S$, and satisfying
$P[E^{2}_{S}\mid E^{1}_{S}]=p_{2}\geq 2/n^{c}$. Then, there exists a non-empty
subset of possible random bits assignments satisfying the following.

  * •

For each $S\in\mathcal{S}$, the events $E^{1}_{S}$ and $E^{2}_{S}$ hold.

  * •

The failure probability of $\mathcal{A}$, when run using such random bits
assignments, is at most $16/(p_{2}\cdot n^{c})$.

###### Proof.

Let $p_{1}$ be the probability that $E^{1}_{S}$ happens. By Lemma 55, with
probability at least $1-1/n^{c}$, each node is able to communicate with the
nodes of at most one designated neighborhood in $\mathcal{S}$. Observe that,
if we restrict to random bits assignments satisfying this condition, we get
that:

  * •

the failure probability increases at most to $2/n^{c}$;

  * •

the probability that $E^{1}_{S}$ holds is still at least $p_{1}/2$;

  * •

the probability that $E^{2}_{S}$ holds, conditioned on $E^{1}_{S}$, is still a
least $p_{2}/2$.

First, we restrict to these random bits. Then, for each $S\in\mathcal{S}$, we
restrict the random bit assignment even further, by taking an assignment at
random among the ones satisfies both $E^{1}_{S}$ and $E^{2}_{S}$. We get that
the failure probability of each node is at most
$\frac{2}{n^{c}}\cdot\frac{2}{p_{1}}\cdot\frac{2}{p_{2}}$, since a node is
able to see at most one neighborhood $S$ where random bits have been
restricted to satisfy $E^{1}_{S}$ and $E^{2}_{S}$, and such an assignment
could have happened with probability at least $p_{1}/2\cdot p_{2}/2$.

By the Markov inequality, and by applying Lemma 52 with suitable constants, by
running $\mathcal{A}$ on the designated node $v$ in $S$, $v$ does not
communicate with any node outside $S$ with probability at least $1/2$. Hence,
$p_{1}=1/2$. We thus get that the failure probability is bounded by
$16/(p_{2}\cdot n^{c})$. ∎

By setting $E^{2}_{S}$ as an event that always holds, we get the following
corollary.

######  Corollary 57.

Let $\mathcal{A}$ be a randomized algorithm with node-averaged complexity
$o(w^{1/(2^{k}-1)}/\log n)$ and failure probability at most $1/n^{c}$, where
$w=w(n)$ is in $O(n)$. Then, there exists a non-empty subset of possible
random bits assignments satisfying the following.

  * •

For each $S\in\mathcal{S}$, by running $\mathcal{A}$ on the designated node
$v$ in $S$, $v$ does not communicate with any node outside $S$.

  * •

The failure probability of $\mathcal{A}$, when run using such random bits
assignments, is at most $16/n^{c}$.

We now prove a statement for deterministic algorithms that run in
$T(n)=o(w^{1/(2^{k}-1)})$, where $w=w(n)$ is in $O(n)$. For this purpose, we
consider the set $\mathcal{S}$ of designated neighborhoods w.r.t. $g(n)=1$ and
some constant $\beta$.

######  Lemma 58.

Let $\mathcal{A}$ be a deterministic algorithm with node-averaged complexity
$T(n)=o(w^{1/(2^{k}-1)})$, where $w=w(n)$ is in $O(n)$. Let $S\in\mathcal{S}$
be a designated neighborhood. Let the ID space be $\\{1,\ldots,n^{q}\\}$, for
some constant $q$ large enough. There are at least $n^{q-2}$ disjoint sets of
IDs such that, for each of them, it is possible to assign the IDs to the nodes
of $S$ such that, by running $\mathcal{A}$ on the designated node $v$ in $S$,
$v$ does not communicate with any node outside $S$.

###### Proof.

From the ID space $\\{1,\ldots,n^{q}\\}$, we can construct $n^{q-1}$ disjoint
sets of $n$ IDs, and for each set we can construct an arbitrary specific ID
assignment that uses only IDs from that set. Let $X$ be the set of such ID
assignments (observe that $|X|=n^{q-1}$).

Let $i$ be the layer of the designated node in $S$. Let $\mathcal{P}$ be the
set containing, for each $j\in\\{1,\ldots,i\\}$, all the compress subpaths of
layer $j$ induced by nodes in $S\setminus\\{v\\}$. We prove that we can
process each subpath $P\in\mathcal{P}$, and discard at most $n$ elements among
the remaining elements in $X$, to make sure that, for all the remaining ID
assignments, there exists at least one node in $P$ running in at most half of
the length of the subpath. Since there are at most $n$ elements in
$\mathcal{P}$, we obtain that there exists a subset of $X$ of size
$n^{q-1}-n^{2}\geq n^{q-2}$ where $v$ cannot see outside $S$, proving the
statement.

We process all subpaths $P\in\mathcal{P}$ in an arbitrary order, and each time
we restrict the set $X$ to make sure that it satisfies the required condition.
Let $j$ be the layer of $P$. Consider the node $v$ at the center of $P$,
breaking ties arbitrarily. Since $P$ is of length at least
$w^{2^{j-1}/(2^{k}-1)}/\beta$ for a fixed constant $\beta$, for $c$ small
enough $v$ is at distance at least $c\cdot w^{2^{j-1}/(2^{k}-1)}$ from the
endpoints of $P$. Let $n^{\prime}$ be the amount of ID assignments that are
still in $X$, and assume that $n^{\prime}\geq n$. We take $n$ arbitrary ID
assignments from $X$, let $Y$ be this set. We apply Corollary 54 on $v$ and
the ID assignments in $Y$, and we obtain that there exists an element $y\in Y$
where the runtime of $v$ is bounded by $c\cdot w^{2^{j-1}/(2^{k}-1)}$ for an
arbitrarily small constant $c$. Now, we can replace $y$ with another element
from $X$, apply the lemma again, and obtain the same result. This operation
can be repeated for $n^{\prime}-n+1$ times, in order to obtain
$n^{\prime}-n+1$ ID assignments in $X$ where the runtime of $v$ is bounded by
$c\cdot w^{2^{j-1}/(2^{k}-1)}$. We discard all the other ID assignments. We
obtain that we removed $n-1$ ID assignments from $X$, and that, in all the
remaining ones, the runtime of $v$ is bounded by $c\cdot
w^{2^{j-1}/(2^{k}-1)}$, that for $c$ small enough is less than half of the
length of $P$. ∎

######  Corollary 59.

Let $\mathcal{A}$ be a deterministic algorithm with node-averaged complexity
$o(w^{1/(2^{k}-1)})$, where $w=w(n)$ is in $O(n)$. Let the ID space be
$\\{1,\ldots,n^{c}\\}$. There are at least $n^{c-3}$ disjoint sets of IDs such
that, for each of them, it is possible to assign the IDs to the nodes of each
$S\in\mathcal{S}$, such that, by running $\mathcal{A}$ on the designated node
$v$ in $S$, $v$ does not communicate with any node outside $S$.

###### Proof.

We split the ID space into $n$ disjoint subsets of size $n^{c-1}$. Note that
$n$ is an upper bound on the elements of $\mathcal{S}$. To each element
$S\in\mathcal{S}$ we assign a different subset. We apply Lemma 58 on each
$S\in\mathcal{S}$, and we obtain that, for each $S\in\mathcal{S}$, there exist
$n^{c-3}$ ID assignments for the whole graph, where the designated node $v$ of
$S$ does not see outside $S$. Since $v$ does not see outside $S$, changing the
IDs outside $S$ does not affect the runtime of $v$. Hence, we can combine the
ID assignments of all the designated neighborhoods to produce $n^{c-3}$ ID
assignments satisfying the requirements. ∎

###  8.3 The $f_{\Pi,k+1}$ Function Given $\mathcal{A}$

#### Function definition.

We now show how to define the function $f_{\Pi,k+1}$ by either using a given
algorithm $\mathcal{A}$ that solves $\Pi$ with randomized node-averaged
complexity $o(w(n)^{1/(2^{k}-1)}/\log n)$, or by using a given algorithm
$\mathcal{A}$ that solves $\Pi$ with deterministic node-averaged complexity
$o(w(n)^{1/(2^{k}-1)})$, where $w(n)\leq c\cdot n$ for a small enough constant
$c>0$ and $n$ large enough. Observe that, by setting $w(n):=c\cdot n$, we
obtain exactly the main goal of this section. However, we prove a generic
statement for all functions $w$, with the hope that such a result could be
useful in the future when studying other complexity regimes.

Recall that the input of the function $f_{\Pi,k+1}$ is a compress path
$P=(H,F_{\mathrm{incoming}},F_{\mathrm{outgoing}},\mathcal{L}_{\mathrm{incoming}})$,
and it is required to produce an independent class for it. As a technicality,
let us mention that, for each compress path $P$, the representative tree
$r(P)$ is well defined, since we can define $f_{\Pi,k+1}$ while being tested
by the testing procedure.

We will define the function $f_{\Pi,k+1}$, as a function of a parameter $n$
that is at least some large enough constant $n_{0}$. For deterministic
algorithms, we first set $n_{0}$ to be the smallest value satisfying that the
running time of $\mathcal{A}$, on all instances of size $n\geq n_{0}$, is at
most $t=w(n)^{1/(2^{k}-1)}/\alpha$, for some constant $\alpha$ to be fixed
later. Such a value exists by the assumption on the node-averaged complexity
of $\mathcal{A}$. Then, we update $n_{0}=\max\\{n_{0},n^{\prime}\\}$, where
$n^{\prime}$ is the value in Corollary 54. For randomized algorithms, we first
set $n_{0}$ to be the smallest value satisfying that the running time of
$\mathcal{A}$, on all instances of size $n\geq n_{0}$, is at most
$t=w(n)^{1/(2^{k}-1)}/(\alpha\log n)$, for some constant $\alpha$ to be fixed
later. Such a value exists by the assumption on the node-averaged complexity
of $\mathcal{A}$. Then, we update $n_{0}=\max\\{n_{0},n^{\prime}\\}$, where
$n^{\prime}$ is the value in Corollary 53.

Let $N_{f}(w)$ be the maximum size of any graph obtained from the function
$\mathrm{pump}_{k}$, as a function of the parameter $w$, when applied to the
graphs constructed in the testing procedure with the function $f$. Then, let
$N(w)$ be the maximum value of $N_{f}(w)$, taken over all possible functions
$f$, again as a function of the parameter $w$. In other words, $N(w)$ is the
maximum size of any graph obtained from the function $\mathrm{pump}_{k}$, as a
function of the parameter $w$, over all possible functions $f$.

In the following, we consider an arbitrary $n$ that is at least $n_{0}$, and
let $w=w(n)$. By Lemma 50, $N(w)=O(w)$. Thus, $N\leq c\cdot n$ for a small
enough constant $c>0$. In the following, we assume $c$ to be small enough so
that $n\geq 16|\Sigma_{\mathrm{out}}|\Delta N+1$.

We define the function $f_{\Pi,k+1}$ on the input
$P=(H,F_{\mathrm{incoming}},F_{\mathrm{outgoing}},\mathcal{L}_{\mathrm{incoming}})$
as follows. First, construct the tree
$T=\mathrm{add}(n,\mathrm{pump}(w,r(P)))$, and let $H^{\prime}$ be the pumped
path corresponding to the nodes of $H$ in $T$. Let $v$ be the designated node
of $H^{\prime}$, and let $e$ be the designated edge of $H^{\prime}$. Let $i$
be the layer number of $v$. The goal is to run $\mathcal{A}$ on $T$ and use
its output on $e$ to define the function $f_{\Pi,k+1}$. Observe that the
output of $\mathcal{A}$, and its runtime, depend on the random bits (if
$\mathcal{A}$ is randomized) and on the ID assignment assigned to the nodes of
$T$. Let $g(n)=\log n$ if $\mathcal{A}$ is randomized, and $g(n)=1$ otherwise.
Let $B$ be the subset of random bits and ID assignments to the nodes of $T$
given by Corollary 57 and Corollary 59. We consider all assignments in $B$,
and we take the output $o$ on $e$ that appears more often (breaking ties
arbitrarily). Observe that this output appears with probability at least
$1/|\Sigma_{\mathrm{out}}|$.

Let
$(H^{\prime},F^{\prime}_{\mathrm{incoming}},F^{\prime}_{\mathrm{outgoing}},\mathcal{L}^{\prime}_{\mathrm{incoming}})$
be the result of applying Lemma 49 on $P$ with parameter $w_{i}$. For each
endpoint $u$ of $H^{\prime}$, we can compute a label-set as follows. Let
$u_{1}$ be the node, among the endpoints of the designated edge $e$, that is
closest to $u$, and let $u_{z}=u$. Consider the subpath $u_{1},\ldots,u_{z}$
of $H^{\prime}$ induced by $u_{1}$, $u_{z}$, and the nodes in between. We
define the label-set of $e$ as $\\{o\\}$. Then, we compute the label-set of
each edge $e_{i}=\\{u_{i},u_{i+1}\\}$, for $i=1,\ldots,z$, by applying
Definition 6 as if the current node $u_{i}$ were to be a single rake node with
outgoing edge $e_{i}$, where $e_{z}$ is defined to be the edge outgoing from
$u$. Observe that the label-sets $L_{1}$ and $L_{2}$ of the endpoints induce
an independent class for $H^{\prime}$, because, for any choice
$(l_{1},l_{2})\in L_{1}\times L_{2}$, by construction, we can pick a feasible
assignment for $P$. By Lemma 49, this independent class is valid also for $H$.

#### Function correctness.

We start by proving the correctness of the function created by using a
deterministic algorithm.

######  Lemma 60.

Assume that the following holds.

  * •

$f_{\Pi,k+1}$ is a function that has been constructed by using trees of size
$n$ and a deterministic algorithm with node-averaged complexity
$o(w^{1/(2^{k}-1)})$, where $w=w(n)$ is in $O(n)$.

  * •

$n\geq\Delta N+1$.

  * •

The ID space is $\\{1,\ldots,n^{c}\\}$, for some large enough constant $c$.

  * •

$((T,v),L)$ is a pair obtained by the testing procedure by using the function
$f_{\Pi,k+1}$.

Let $T^{\prime}=\mathrm{pump}_{k}(w,T)$. Then

  * •

$T^{\prime}$ has at most $N$ nodes, where $N=\Theta(w(n))$, and

  * •

there exists a set $\mathcal{X}$ containing $O(n^{c-4})$ disjoint sets of IDs

satisfying that, for each $X\in\mathcal{X}$, it is possible to assign IDs to
the nodes of $T^{\prime}$, such that:

  * •

All the IDs are from $X$.

  * •

There exists a set of nodes $D$ in $T^{\prime}$ that, by running
$\mathcal{A}$, they do not see outside $T^{\prime}$.

  * •

Any labeling of $T^{\prime}$ that agrees with the outputs of the nodes of $D$
restricts the labels on the edge incident to the node of $T^{\prime}$ that
corresponds to $v$ to a subset of $L$.

###### Proof.

Recall that $v$ is a temporary node, and hence $T^{\prime}$ contains at least
one temporary node. Thus, we can construct
$T^{\prime\prime}=\mathrm{add}(n,T^{\prime})$.

Let $\mathcal{L}$ be the partial labeling obtained by putting the most
probable output (as previously defined) on each designated edge of
$T^{\prime\prime}$.

We process the designated neighborhoods in $T^{\prime\prime}$ one by one, and
each time we assign the IDs in the neighborhood such that: the designated node
does not see outside the designated neighborhood; the designated edge has the
most probable output; the assigned IDs are not used in the rest of the graph.

Let $S$ be the current designated neighborhood to which we want to assign IDs.
Observe that, by Corollary 59, there are at least
$n^{c-3}/|\Sigma_{\mathrm{out}}|$ disjoint ID assignments such that the
designated edge gets the required output. Since there are at most $n$ IDs that
have been already used to assign IDs to previously-handled designated
neighborhoods, there are still at least $n^{c-3}/|\Sigma_{\mathrm{out}}|-n>0$
possible choices that satisfy the requirements.

We showed that there exists one ID assignment that satisfies the above
requirements. Note that, by repeating this procedure with unused IDs, it is
possible to construct $n^{c-4}/|\Sigma_{\mathrm{out}}|=O(n^{c-4})$ such ID
assignments.

Since the designated nodes do not see outside the designated neighborhoods, we
get that there exist $O(n^{c-4})$ ID assignments (using disjoint sets of IDs)
such that the algorithm outputs a labeling that agrees with $\mathcal{L}$. By
Lemma 49, and by the definition of $f_{\Pi,k+1}$, we get that the labels
allowed for the edge incident to the temporary node are a subset of $L$. ∎

######  Corollary 61.

Let $\mathcal{A}$ be a deterministic algorithm with node-averaged complexity
$o(w^{1/(2^{k}-1)})$, where $w=w(n)$ is in $O(n)$. The function $f_{\Pi,k+1}$
constructed using $\mathcal{A}$ passes the testing procedure.

###### Proof.

Assume that the testing procedure fails. This means that an empty class on
some node $v$ in some representative tree $T$ is obtained. A necessary
condition for obtaining an empty class is that $T$ contains at least a
compress path (otherwise, the function would not even be used), implying that
$T$ contains at least two temporary nodes. Let $L_{1},\ldots,L_{d}$ be the
label-sets assigned to the incoming edges of $v$. We use Lemma 60 to construct
$d$ pairs
$((T^{\prime}_{1},v_{1}),L_{1}),\ldots,((T^{\prime}_{d},v_{d}),L_{d})$ with
disjoint ID assignments, and we merge them into a single tree
$T^{\prime\prime}$ of at most $\Delta N\leq n$ nodes by identifying nodes
$v_{1},\ldots,v_{d}$ into a single node $v^{\prime}$. If $v$ has degree $d+1$,
we add an additional neighbor to $v^{\prime}$, and the number of nodes is now
at most $\Delta N+1\leq n$. Observe that, in $T^{\prime\prime}$, the following
holds. Node $v^{\prime}$ has the same degree as $v$, and $d$ incident edges
are restricted to have the label-sets $L_{1},\ldots,L_{d}$, if
$T^{\prime\prime}$ were to be of size exactly $n$. However, note that we can
increase the number of nodes to be exactly $n$ by using
$\mathrm{add}(n,T^{\prime\prime})$. This is doable since $T^{\prime\prime}$
contains at least one temporary node different from $v^{\prime}$ (since, as
argued, $T$ contains at least two temporary nodes). By the definition of
class, and by the assumption that $v$ has an empty class, there is no valid
labeling for the edges of $v$, which is a contradiction on the correctness of
$\mathcal{A}$. ∎

We now prove the correctness of the function created by using a randomized
algorithm.

######  Lemma 62.

Assume that the following holds.

  * •

$f_{\Pi,k+1}$ is a function that has been constructed by using trees of size
$n$ and a randomized algorithm with node-averaged complexity
$o(w^{1/(2^{k}-1)}/\log n)$, where $w=w(n)$ is in $O(n)$.

  * •

$n\geq 16|\Sigma_{\mathrm{out}}|N+1$.

  * •

$C$ is a class obtained by the testing procedure on some representative tree
$T$ that contains at least one temporary node $v$, by using the function
$f_{\Pi,k+1}$.

Let $T^{\prime}=\mathrm{pump}_{k}(w,T)$ and
$T^{\prime\prime}=\mathrm{add}(n,T^{\prime})$. Then,

  * •

$T^{\prime}$ has at most $N$ nodes, where $N=\Theta(w(n))$.

Moreover, by running $\mathcal{A}$ on $T^{\prime\prime}$, with non-zero
probability,

  * •

all nodes in $T^{\prime}$ do not fail, and

  * •

there exists a node $u$ in $T^{\prime}$ that has an output compatible with the
class $C$ (this, in particular, implies that $C$ is not empty).

###### Proof.

Let $\mathcal{L}$ be the partial labeling obtained by putting the most
probable output (as previously defined) on each designated edge of
$T^{\prime\prime}$.

We run $\mathcal{A}$ on $T^{\prime\prime}$ by using the random bits given by
Corollary 57, restricted to the case in which, for each $S\in\mathcal{S}$, the
designated edge gets the most probable output. That is, we apply Lemma 56 by
setting the event $E^{2}_{S}$ to the event in which the designated edge gets
the most probable output when restricted to the random bit assignments given
by Corollary 57. Note that $p_{2}=1/|\Sigma_{\mathrm{out}}|$. We get that the
failure probability of $\mathcal{A}$ is at most
$16/(1/|\Sigma_{\mathrm{out}}|\cdot n^{c})=16|\Sigma_{\mathrm{out}}|/n^{c}$.
By a union bound, the probability that all nodes in $T^{\prime}$ succeed is at
least $1-N\cdot 16|\Sigma_{\mathrm{out}}|/n^{c}\geq 1-N\cdot
16|\Sigma_{\mathrm{out}}|/n\geq 1-N\cdot 16|\Sigma_{\mathrm{out}}|/(N\cdot
16|\Sigma_{\mathrm{out}}|+1)>0$. Hence, by the probabilistic method, there
exists an assignment of output labels that is valid for all the nodes of
$T^{\prime}$ and that agrees with $\mathcal{L}$. By Lemma 49, and by the
definition of $f_{\Pi,k+1}$, we get that the output on the edges incident to
$u$ is compatible with $C$. ∎

######  Corollary 63.

Let $\mathcal{A}$ be a randomized algorithm with node-averaged complexity
$o(w^{1/(2^{k}-1)}/\log n)$, where $w=w(n)$ is in $O(n)$. The function
$f_{\Pi,k+1}$ constructed using $\mathcal{A}$ passes the testing procedure.

###### Proof.

Assume that the testing procedure fails. This means that an empty class on
some representative tree $T$ is obtained. Note that there must be at least one
compress path, otherwise the function is not even used. This implies that $T$
contains at least one temporary node. By Lemma 62, any class obtained by the
testing procedure is non-empty, which is a contradiction. ∎

##  9 Open Questions

We conclude with some open questions. We showed that all problems that have
$O(\log n)$ worst-case complexity can be solved with $O(\log^{*}n)$ node-
averaged complexity. We leave open to determine for which problems this can be
improved.

######  Open Problem 1.

For which LCLs with $O(\log n)$ worst-case complexity can we obtain
$o(\log^{*}n)$ node-averaged complexity?

We showed that all problems that have worst-case complexity $\Theta(n^{1/k})$
must have node-averaged complexity $\Omega(n^{1/(2^{k}-1)}/\log n)$. We
conjecture that the $\log n$ factor is an artefact of our proof technique and
that it should not be there.

######  Open Problem 2.

Can we prove a lower bound of $\Omega(n^{1/(2^{k}-1)})$ rounds for the node-
averaged complexity of all problems with worst-case complexity
$\Theta(n^{1/k})$?

We showed that for some LCL problems that have worst-case complexity
$\Theta(n^{1/k})$, we can provide an algorithm with node-averaged complexity
$O(n^{1/(2^{k}-1)})$. It is not clear if this can be done for all problems
with worst-case complexity $\Theta(n^{1/k})$.

######  Open Problem 3.

Can we prove an upper bound of $O(n^{1/(2^{k}-1)})$ rounds for the node-
averaged complexity of all problems that have worst-case complexity
$\Theta(n^{1/k})$?

######  Open Problem 4.

Can we prove a lower bound of $\Omega(n^{1/k})$ rounds for the node-averaged
complexity of some problems that have worst-case complexity $\Theta(n^{1/k})$?

## References

  * [1] Yehuda Afek, Shay Kutten, and Moti Yung.  The local detection paradigm and its application to self-stabilization.  Theor. Comput. Sci., 186(1-2):199–229, 1997.  doi:10.1016/S0304-3975(96)00286-1.
  * [2] Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela.  The distributed complexity of locally checkable problems on paths is decidable.  In Proc. 38th ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 262–271. ACM Press, 2019.  arXiv:1811.01672, doi:10.1145/3293611.3331606.
  * [3] Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, and Jukka Suomela.  Efficient classification of locally checkable problems in regular trees.  In Proc. 36th International Symposium on Distributed Computing,(DISC 2022), pages 8:1–8:19, 2022.  doi:10.4230/LIPIcs.DISC.2022.8.
  * [4] Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, and Jukka Suomela.  Classification of distributed binary labeling problems.  In Proc. 34th International Symposium on Distributed Computing (DISC 2020), volume 179 of LIPIcs, pages 17:1–17:17. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020.  doi:10.4230/LIPIcs.DISC.2020.17.
  * [5] Alkida Balliu, Sebastian Brandt, Manuela Fischer, Rustam Latypov, Yannic Maus, Dennis Olivetti, and Jara Uitto.  Exponential speedup over locality in MPC with optimal memory.  In 36th International Symposium on Distributed Computing, (DISC 2022), pages 9:1–9:21, 2022.  doi:10.4230/LIPIcs.DISC.2022.9.
  * [6] Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studený, Jukka Suomela, and Aleksandr Tereshchenko.  Locally checkable problems in rooted trees.  In Proc. 40th ACM Symposium on Principles of Distributed Computing (PODC 2021), pages 263–272, 2021.  doi:10.1145/3465084.3467934.
  * [7] Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela.  How much does randomness help with locally checkable problems?  In Proc. 39th ACM Symposium on Principles of Distributed Computing (PODC 2020), pages 299–308. ACM Press, 2020.  arXiv:1902.06803, doi:10.1145/3382734.3405715.
  * [8] Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela.  Almost global problems in the LOCAL model.  Distributed Comput., 34(4):259–281, 2021.  doi:10.1007/s00446-020-00375-2.
  * [9] Alkida Balliu, Keren Censor-Hillel, Yannic Maus, Dennis Olivetti, and Jukka Suomela.  Locally checkable labelings with small messages.  In 35th International Symposium on Distributed Computing, DISC 2021, pages 8:1–8:18, 2021.  doi:10.4230/LIPIcs.DISC.2021.8.
  * [10] Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, and Dennis Olivetti.  Node and edge averaged complexities of local graph problems.  In Proc. 41st ACM Symp. on Principles of Distributed Computing (PODC), pages 4–14, 2022.
  * [11] Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, and Jukka Suomela.  New classes of distributed time complexity.  In Proc. 50th ACM Symposium on Theory of Computing (STOC 2018), pages 1307–1318. ACM Press, 2018.  arXiv:1711.01871, doi:10.1145/3188745.3188860.
  * [12] Alkida Balliu, Juho Hirvonen, Dennis Olivetti, and Jukka Suomela.  Hardness of minimal symmetry breaking in distributed computing.  In Proc. 38th ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 369–378. ACM Press, 2019.  arXiv:1811.01643, doi:10.1145/3293611.3331605.
  * [13] Leonid Barenboim, Michael Elkin, and Fabian Kuhn.  Distributed $(\Delta+1)$-coloring in linear (in $\Delta$) time.  SIAM J. on Computing, 43(1):72–95, 2015.
  * [14] Leonid Barenboim and Yaniv Tzur.  Distributed symmetry-breaking with improved vertex-averaged complexity.  In Proc. 20th Int. Conf. on Distributed Computing and Networking (ICDCN), pages 31–40, 2019.
  * [15] Sebastian Brandt, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Patric R. J. Östergård, Christopher Purcell, Joel Rybicki, Jukka Suomela, and Przemyslaw Uznanski.  LCL problems on grids.  In Proc. 36th ACM Symposium on Principles of Distributed Computing (PODC 2017), pages 101–110, 2017.  doi:10.1145/3087801.3087833.
  * [16] Yi-Jun Chang.  The complexity landscape of distributed locally checkable problems on trees.  In Proc. 34th International Symposium on Distributed Computing (DISC 2020), volume 179 of LIPIcs, pages 18:1–18:17. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020.  doi:10.4230/LIPIcs.DISC.2020.18.
  * [17] Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto.  Distributed edge coloring and a special case of the constructive lovász local lemma.  ACM Trans. Algorithms, 16(1):8:1–8:51, 2020.
  * [18] Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie.  An exponential separation between randomized and deterministic complexity in the LOCAL model.  SIAM J. Comput., 48(1):122–143, 2019.  doi:10.1137/17M1117537.
  * [19] Yi-Jun Chang and Seth Pettie.  A time hierarchy theorem for the LOCAL model.  SIAM J. Comput., 48(1):33–69, 2019.  doi:10.1137/17M1157957.
  * [20] Yi-Jun Chang, Jan Studený, and Jukka Suomela.  Distributed graph problems through an automata-theoretic lens.  In Proc. 28th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2021), LNCS. Springer, 2021\.  arXiv:2002.07659.
  * [21] Soumyottam Chatterjee, Robert Gmyr, and Gopal Pandurangan.  Sleeping is efficient: MIS in _O_(1)-rounds node-averaged awake complexity.  In Proc. 39th ACM Symp. on on Principles of Distributed Computing (PODC), pages 99–108, 2020.
  * [22] Laurent Feuilloley.  How long it takes for an ordinary node with an ordinary ID to output?  In Proc. 24th Int. Coll. on Structural Information and Communication Complexity (SIROCCO), volume 10641, pages 263–282, 2017.
  * [23] Manuela Fischer and Mohsen Ghaffari.  Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy.  In Proc. 31st International Symposium on Distributed Computing (DISC 2017), volume 91 of LIPIcs, pages 18:1–18:16, 2017.  doi:10.4230/LIPIcs.DISC.2017.18.
  * [24] Christoph Grunau, Václav Rozhon, and Sebastian Brandt.  The landscape of distributed complexities on trees and beyond.  In Proc. 41st ACM Symposium on Principles of Distributed Computing (PODC 2022), pages 37–47, 2022.  doi:10.1145/3519270.3538452.
  * [25] Öjvind Johansson.  Simple distributed _Delta_ +1-coloring of graphs.  Inf. Process. Lett., 70(5):229–232, 1999.
  * [26] Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer.  Local computation: Lower and upper bounds.  J. ACM, 63(2):17:1–17:44, 2016.
  * [27] Nathan Linial.  Locality in distributed graph algorithms.  SIAM J. Comput., 21(1):193–201, 1992.
  * [28] Gary L. Miller and John H. Reif.  Parallel tree contraction and its application.  In 26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, USA, 21-23 October 1985, pages 478–489. IEEE Computer Society, 1985.  doi:10.1109/SFCS.1985.43.
  * [29] Moni Naor and Larry J. Stockmeyer.  What can be computed locally?  SIAM J. Comput., 24(6):1259–1277, 1995.  doi:10.1137/S0097539793254571.
  * [30] Václav Rozhoň and Mohsen Ghaffari.  Polylogarithmic-time deterministic network decomposition and distributed derandomization.  In Proc. 52nd ACM Symp. on Theory of Computing (STOC), pages 350–363, 2020.

##  Appendix A Additional Related Work About LCLs

LCLs were introduced by Naor and Stockmeyer [29], but locally checkable
problems were studied in the distributed setting even before [1]. Since then,
LCL problems have been studied a lot, and we now known, for different possible
topologies of graphs, what kind of worst-case complexities are possible.

#### Paths and cycles.

We know that in paths and cycles there are only three possible complexities:
$O(1)$, $\Theta(\log^{*}n)$, $\Theta(n)$ [29, 18]. Moreover, we know that
randomness does not help to solve problems faster.

#### Trees.

The possible deterministic complexities in trees are $O(1)$,
$\Theta(\log^{*}n)$, $\Theta(\log n)$, and $\Theta(n^{1/k})$ for all integer
$k\geq 1$; randomness either helps exponentially or not at all, and only for
problems with deterministic complexity $\Theta(\log n)$, that hence have
randomized complexity either $\Theta(\log n)$ or $\Theta(\log\log n)$ [24, 12,
18, 19, 8, 16].

#### General graphs.

In general graphs, some _complexity gaps_ that hold in the case of trees still
hold, but now there are also many dense areas; while in trees randomness
either helps exponentially or not at all, there are cases on general graphs
where randomness helps only polynomially [19, 18, 23, 30, 11, 7].

#### LCLs in other settings.

On $d$-dimensional balanced toroidal grids, it is known that the only possible
complexities are $O(1)$, $O(\log^{*}n)$, and $\Theta(n^{1/d})$ (even by
allowing randomness) [15].

For problems that, in the black-white formalism (as defined in Section 3), can
be expressed by using at most two labels, on regular trees the only possible
deterministic complexities are $O(1)$, $\Theta(\log n)$ and $\Theta(n)$,
implying that any LCL with complexity $\Theta(\log^{*}n)$ needs to be
expressed with at least $3$ labels [4].

It is known that any LCL on trees that can be solved in $T$ rounds in the
LOCAL model of distributed computing can be solved in $O(T)$ rounds in the
CONGEST model; it is also known that this does not hold if we consider general
graphs [9].

On _rooted_ trees, it is known that all possible complexities are $O(1)$,
$\Theta(\log^{*}n)$, $\Theta(\log n)$, $\Theta(n^{1/k})$ for all integer
$k\geq 1$, but perhaps surprisingly, randomness never helps in solving
problems faster [6].

LCLs have been studied also in other models of interest such as MPC [5].

#### Decidability.

LCLs have been studied not only from a point of view of complexity theory.
Researchers tried also to address the following questions. Given a specific
LCL, can we decide its time complexity with a centralized algorithm? Is it
possible to automate the design of algorithms for solving LCLs?

In general, the complexity of an LCL is not decidable: even on unlabeled non-
toroidal grid graphs it is undecidable whether the complexity of an LCL is
$O(1)$ [29]. However, there are some positive results in more restricted but
still interesting settings.

On paths and cycles, it is possible to determine what is the time complexity
of a given problem, but it becomes EXPTIME-hard if some input is provided to
the nodes [29, 15, 20, 2, 16].

In unlabeled toroidal grids, it is decidable whether the complexity of an LCL
is $O(1)$, but it is undecidable whether its complexity is $\Theta(\log^{*}n)$
or $\Theta(n)$ [15].

On trees, given an LCL, it is possible to decide on which side of the gap
$\omega(\log n)$ – $n^{o(1)}$ its complexity lies. Moreover, it is decidable
if an LCL has complexity $\Theta(n^{1/k})$ for some $k$, and it is also
possible to determine the exact value of $k$ [19, 16], but the algorithm is
very far from being practical. However, if we restrict to regular trees with
no inputs, then there is a practical polynomial-time algorithm (in the size of
the description of the LCL problem) for deciding if an LCL has complexity
$\Theta(n^{1/k})$ and determining the exact value of $k$ [3]. Similarly, for
rooted trees, there are efficient algorithms for determining the optimal
asymptotic complexity of a given LCL [6, 3]. On unrooted regular trees with no
input, if we restrict to problems that can be expressed by using at most two
labels in the black-white formalism, the deterministic complexity of a problem
is decidable [4].

It is still an open question whether, on trees, we can obtain decidability for
the lower complexities, e.g., it is unknown whether we can decide if an LCL on
trees can be solved in $O(1)$ rounds or if it requires $\Omega(\log^{*}n)$
rounds, and whether it can be solved in $O(\log^{*}n)$ rounds or if it
requires $\Omega(\log n)$ with deterministic algorithms.

##  Appendix B An Algorithm For Solving All LCLs in $O(D)$ Rounds

In order to give more intuition about the generic method that can be used to
solve LCL problems, we repropose a simplified setting already presented in
[9], where we restrict a bit the class of problems that we consider, as
follows. We are given a tree of constant maximum degree, where to each edge is
assigned an input label that comes from a finite set, and the goal is to
assign an output label to each edge, also from a finite set, in such a way
that, for each node, the multiset of incident input-output pairs of labels is
contained in a list of given allowed configurations (this list is the same for
all nodes). In other words, in this simplified setting, an LCL problem is
described by providing a list of allowed configurations $C$, that are
multisets of input-output pairs of labels. We now describe a procedure,
already presented in [9], that solves any problem of this form in $O(D)$
rounds, where $D$ is the diameter of the tree. The procedure works as follows:

  1. 1.

Each leaf node $v$, as a function of the input label $\ell_{i}$ of its
incident edge $e$ and the list of allowed configurations $C$, computes the set
$S_{v}$ of output labels $\ell_{o}$ satisfying that the multiset
$\\{(\ell_{i},\ell_{o})\\}$ is in $C$, that is, $v$ computes the set $S_{v}$
of output labels $\ell_{o}$ that, if assigned to $e$, would make $v$ happy.

  2. 2.

Each leaf $v$ sends the set $S_{v}$ to its neighbor.

  3. 3.

Leaves are removed from the tree. Let $L$ be the set of nodes that became
leaves after the removal operation. Each node $v\in L$ proceeds as follows.
Let $u_{1},\ldots,u_{d}$ be the neighbors of $v$ that got removed in previous
steps, let $\ell_{i_{1}},\ldots,\ell_{i_{d}}$ be the input labels on the edges
connecting node $v$ to the nodes $u_{1},\ldots,u_{d}$, and let $\ell_{i}$ be
the input label connecting $v$ to its neighbor that is still present. Node $v$
computes the set $S_{v}$ of output labels $\ell_{o}$ satisfying that there
exists a choice $(\ell_{o_{1}},\ldots,\ell_{o_{d}})\in
S_{u_{1}}\times\ldots\times S_{u_{d}}$ such that the multiset
$\\{(\ell_{i},\ell_{o}),(\ell_{i_{1}},\ell_{o_{1}}),\ldots,(\ell_{i_{d}},\ell_{o_{d}})\\}$
is in $C$. In other words, node $v$ computes the set $S_{v}$ of output labels
for its remaining edge satisfying that, even if the output from $S_{v}$ is
chosen adversarially, there is still a choice that $v$ can make, over the sets
received from its removed neighbors, that would give an assignment of labels
that makes $v$ happy. Then, node $v$ sends $S_{v}$ to its remaining neighbor.

  4. 4.

Repeat step 3 until the graph is empty.

  5. 5.

The last removed node chooses a label from each received set, in such a way
that the resulting multiset of input-output pairs of labels is a configuration
in $C$. (It may happen that two neighboring nodes get removed last, at the
same time, but this case can be handled in a similar way.)

  6. 6.

Removed nodes are put back in reverse order. Observe that, when a node $v$ is
put back, the output label $\ell_{o}$ of the edge connecting $v$ to its only
neighbor that is currently present has already been assigned, and that this
output label $\ell_{o}$ is in $S_{v}$. Node $v$ picks a label from the sets
assigned to the edges connecting $v$ to its other neighbors (that is,
neighbors that are going to be put back in the next step) in a way that is
compatible with $\ell_{o}$.

It is not difficult to see that this algorithm computes a correct solution for
the problem, assuming that the computed sets never become empty, that is, as
long as, for each $v\in V$, $S_{v}\neq\emptyset$. Also, it is clear that the
time complexity of this algorithm is $O(D)$. It has been shown in [9] that, if
it happens that some node $v$ gets $S_{v}=\emptyset$, then it means that the
problem is unsolvable. Moreover, [9] showed that by following this algorithm,
we get a generic way to solve all problems in $O(D)$ rounds that is actually
bandwidth efficient, since the sets that are sent at each step have constant
size.

#### Improving the round complexity.

The previously described procedure shows how to solve all (solvable) problems
in $O(D)$ rounds, which is nice for the CONGEST model, but is a trivial result
in the LOCAL model. Moreover, the diameter $D$ could be as high as
$\Omega(n)$, and for some problems this complexity may be suboptimal. Hence,
in some cases we would like to obtain a faster algorithm, and this is what has
been shown in [19, 16]. The idea of [19, 16] is that, if, instead of removing
only nodes of degree $1$ at each step, we also sometimes remove nodes of
degree $2$ as well, then it takes less steps to obtain an empty graph. One of
the issues to handle when running this modified procedure is that we now have
to find a way to assign sets to nodes of degree $2$, which may form long
paths, and this is the part that turns out to be quite challenging.

#### Restricting to a specific kind of LCLs.

In order to prove our results, we use and extend ideas presented in [19, 16,
9]. In particular, in [9] it has been shown that, in bounded-degree trees, if
an LCL problem has time complexity $T$ in the LOCAL model, then it has time
complexity $O(T)$ in the CONGEST model, both for deterministic and randomized
worst-case complexities. In order to show this result, the authors of [9] not
only extended the results of [19, 16], but also provided a more accessible
version of some of the proofs of [19, 16]. The reason why these proofs are
more accessible is that [9] does not show results for standard LCLs, but only
for a restriction of those, that are LCLs that can be expressed in a formalism
called black-white. Importantly, the authors also showed that, if we restrict
to trees, for any standard LCL (LCLs as they are usually defined in the
literature), we can define an LCL in the black-white formalism that has the
same complexity of the original one, up to an _additive_ constant. In other
words, considering LCLs in the black-white formalism is not really a
restriction if the graph class we are working on is trees (in general graphs
this turns out to not be the case). In this paper, we follow a similar route
of [9]: in order to keep our proofs more accessible we prove our statements
for LCLs expressed in the black-white formalism, but we also prove that, for
any standard LCL, we can define an LCL in the black-white formalism that has
the same node-averaged complexity of the original one, up to a
_multiplicative_ constant factor, implying that our results hold for all LCLs
as well. This equivalence is shown in Lemma 68.

##  Appendix C Different Ways to Define LCLs

In this section we prove an equivalence, for node-averaged complexity, between
different definitions of LCLs. We start by providing the standard definition
of LCLs, that in the following we will call standard LCLs.

#### Locally Checkable Labeling problems.

An LCL problem $\Pi$ is defined as a tuple
$(\Sigma_{\mathrm{in}},\Sigma_{\mathrm{out}},C,r)$, where:

  * •

$\Sigma_{\mathrm{in}}$ and $\Sigma_{\mathrm{out}}$ are finite sets of labels
that represent the possible input and output labels.

  * •

The parameter $r\geq 1$ is an integer, and it represents the so-called
_checkability radius_ of the LCL problem $\Pi$.

  * •

$C$ is a finite set of labeled graphs that represent allowed neighborhoods,
and more precisely $C$ is a finite set of pairs $(H,v)$, where:

    * –

$H=(V_{H},E_{H})$ is a graph, and $v\in V_{H}$.

    * –

The eccentricity of $v$ in $H$ is at most $r$.

    * –

To each pair $(v,e)\in V_{H}\times E_{H}$ is assigned a label
$\ell_{\mathrm{in}}\in\Sigma_{\mathrm{in}}$ and a label
$\ell_{\mathrm{out}}\in\Sigma_{\mathrm{out}}$.

Solving an LCL problem $\Pi$ on a graph $G=(V,E)$ means that:

  * •

To each node-edge pair $(v,e)\in V\times E$ is assigned a label
$i(e)\in\Sigma_{\mathrm{in}}$.

  * •

The task is to assign a label $o(e)\in\Sigma_{\mathrm{out}}$ to each node-edge
pair $(v,e)\in V\times E$ such that, for each node $v\in V$, it holds that the
(labeled) graph $N^{r}_{v}$ induced by $v$’s radius-$r$ neighborhood is in
$C$, that is, $N^{r}_{v}$ is isomorphic to a (labeled) graph contained in $C$.

#### Node-edge formalism.

Using the black-white formalism (as defined in Section 3) requires the graph
to be properly $2$-colored. We now describe a formalism, called node-edge,
that does not have this requirement. We will soon show an equivalence between
the node-edge formalism and the black-white formalism. A problem $\Pi$
described in the node-edge formalism is a tuple
$(\Sigma_{\mathrm{in}},\Sigma_{\mathrm{out}},C_{N},C_{E})$, where:

  * •

$\Sigma_{\mathrm{in}}$ and $\Sigma_{\mathrm{out}}$ are finite sets of labels.

  * •

$C_{N}$ and $C_{E}$ are both multisets of pairs, where each pair
$(\ell_{\mathrm{in}},\ell_{\mathrm{out}})$ is in
$\Sigma_{\mathrm{in}}\times\Sigma_{\mathrm{out}}$. The multisets in $C_{E}$
have size exactly $2$.

Solving a problem $\Pi$ on a graph $G$ means that:

  * •

To each node-edge pair $(v,e)\in V\times E$ is assigned a label
$i(e)\in\Sigma_{\mathrm{in}}$.

  * •

The task is to assign a label $o(e)\in\Sigma_{\mathrm{out}}$ to each node-edge
pair $(v,e)\in V\times E$ such that, for each node $v\in V$ (resp. each edge
$e\in E$) it holds that the multiset of incident input-output pairs is in
$C_{V}$ (resp. in $C_{E}$).

#### Equivalence between black-white and node-edge formalisms.

Observe that, if we focus only on what is a problem, and we forget about what
it means to solve a problem, it is clear that the node-edge formalism is a
subcase of the more general black-white formalism. In fact, it is easy to see
that a problem $\Pi$ in the node-edge formalism implicitly defines also a
problem $\Pi^{\prime}$ in the black-white formalism, while a problem
$\Pi^{\prime}$ in the black-white formalism implicitly defines also a problem
$\Pi$ in the node-edge formalism if it satisfies that $C_{B}$ contains only
multisets of size exactly $2$.

Moreover, it has been show in [9] that also the time complexities of $\Pi$ and
$\Pi^{\prime}$ are related. In fact, one can prove that, given an algorithm
$A$ for $\Pi$, we can define a new algorithm $A^{\prime}$ for $\Pi^{\prime}$
with the same asymptotic worst-case round complexity, and vice versa.

We now describe the ideas that show that, given an algorithm $A^{\prime}$ for
$\Pi^{\prime}$, we can use it to solve $\Pi$ (the other direction can be shown
in a similar way). The idea is to simulate the algorithm for $\Pi^{\prime}$ on
a virtual graph $G^{\prime}$, defined as a function of the real graph
$G=(V,E)$ as follows. Let $G^{\prime}=(W\cup B,E^{\prime})$, where $W=V$,
$B=E$, and we connect $v\in V$ with $e\in B$ if $v\in e$. In other words,
original nodes are white, and we add a black node in the middle of each
original edge. Observe that, by solving $\Pi^{\prime}$ on $G^{\prime}$, and
then mapping the output obtained for the edges of $G^{\prime}$ to the node-
edge pairs of $G$, we also solve $\Pi$ on $G$. Also, observe that simulating
the execution of a $T$ round algorithm for $G^{\prime}$ only costs $T/2+O(1)$
rounds on $G$.

#### Equivalence between standard LCLs and LCLs in the node-edge formalism.

In [9] it has been shown that, given a standard LCL $\Pi$ on trees, it is
possible to define a node-edge checkable problem $\Pi^{\prime}$ satisfying
that, given a solution for $\Pi$, it is possible to spend $O(1)$ rounds to
solve $\Pi^{\prime}$, and vice versa.

######  Lemma 64 ([9]).

For any LCL problem $\Pi$ on trees with checkability radius $r=O(1)$ we can
define a node-edge checkable problem $\Pi^{\prime}$ that satisfies the
following:

  * •

There exists an $O(1)$-rounds algorithm that, given in input a solution for
$\Pi^{\prime}$, outputs a solution for $\Pi$.

  * •

There exists an $O(1)$-rounds algorithm that, given in input a solution for
$\Pi$, outputs a solution for $\Pi^{\prime}$.

By combining this lemma with the equivalence that we discussed before, we
obtain that by studying the worst-case complexity of LCL problems on trees in
the black-white formalism is not a restriction, and hence we get results that
hold for LCLs in the more general form. Figure 14 shows an example of an LCL
problem defined in different formalisms. In the following we show a similar
statement for the node-averaged complexity of LCLs.

Figure 14: a) In the maximal matching problem, a node is either matched or all
its neighbors are matched. This can be described as an LCL by letting each
edge be either labeled $\\{M,M\\}$ or $\\{U,U\\}$, and then listing all
possible valid radius-$2$ neighborhoods. b) The maximal matching problem
encoded in the node-edge formalism. One way is to require unmatched nodes to
orient all their edges outgoing, and then require all nodes with at least one
incoming edge to be matched. These constraints can be given in the node-edge
formalism. c) The $2$-colored graph in which the maximal matching problem has
the same complexity as in the node-edge setting.

#### Equivalence between standard LCLs and black-white formalism for node-
averaged complexity.

In order to prove that we can restrict to the black-white formalism also for
the case of node-averaged complexity, we first prove an equivalence between
standard LCLs and the node-edge formalism, and then we prove an equivalence
between the node-edge formalism and the black-white formalism.

In the case of worst case complexity, if we have an algorithm $A_{1}$ that
produce a result in $T_{1}$ rounds, and we have a different algorithm $A_{2}$
that takes the output of $A_{1}$ in input and produces a result in $T_{2}$
rounds, then we can execute $A_{2}$ after $A_{1}$ and obtain a running time of
$T_{1}+T_{2}$. For node-averaged complexity, unfortunately, the same does not
hold. Nevertheless we can achieve something similar.

######  Lemma 65.

Suppose that we have an algorithm $A_{1}$ with node-averaged complexity
$T_{1}$, and an algorithm $A_{2}$ with worst-case complexity $T_{2}$. Consider
the algorithm $A_{3}$ obtained by combining $A_{1}$ and $A_{2}$, where nodes
execute $A_{2}$ only after all nodes in their $T_{2}$ radius neighborhood
terminated the execution of $A_{1}$. The node-averaged complexity of $A_{3}$
is $O(T_{1}\cdot\Delta^{T_{2}})$.

###### Proof.

We show a charging scheme that satisfies that the sum of the charges is an
upper bound on the sum of the running times of the nodes. For each node $v$ of
the graph, let $t(v)$ be the last node in the $T_{2}$-radius neighborhood of
$v$ that terminates the execution of $A_{1}$, break ties arbitrarily. We
charge the running time of $v$ in $A_{3}$ to $t(v)$. Observe that each node is
charged $O(\Delta^{T_{2}})$ times, and that the sum of the running times in
$A_{1}$ of the nodes charged at least once is $O(n\cdot T_{1})$. Hence, the
sum of the charges, and the running times in $A_{3}$, is $O(n\cdot
T_{1}\cdot\Delta^{T_{2}})$, implying that the node-averaged complexity of
$A_{3}$ is $O(T_{1}\cdot\Delta^{T_{2}})$, as required. ∎

We are now ready to prove an equivalence, for node-averaged complexity,
between standard LCLs and LCLs in the node-edge formalism.

######  Lemma 66.

For any LCL problem $\Pi$ on trees with checkability radius $r$ and node-
averaged complexity $T$ we can define a node-edge checkable problem
$\Pi^{\prime}$ with node-averaged complexity $\Theta(T)$.

###### Proof.

We apply Lemma 65 where $T_{1}$ is the node-averaged complexity of the given
LCL problem $\Pi$, and $T_{2}$ is the worst-case time complexity required to
convert a solution for $\Pi$ into a solution of its equivalent node-edge
checkable variant. By Lemma 64 we have that $T_{2}=O(1)$. Since $\Delta=O(1)$,
then the claim follows. ∎

We now prove an equivalence, for node-averaged complexity, between LCLs in the
node-edge formalism and LCLs in the black-white formalism.

######  Lemma 67.

For any node-edge checkable LCL problem $\Pi$ on trees with node-averaged
complexity $T$ we can define an LCL $\Pi^{\prime}$ in the black-white
formalism with node-averaged complexity $\Theta(T)$.

###### Proof.

Let $\Pi=(\Sigma_{\mathrm{in}},\Sigma_{\mathrm{out}},C_{N},C_{E})$. We define
$\Pi^{\prime}=\Pi$, that is, the input and output labels are exactly the same,
the white constraint of $\Pi^{\prime}$ is $C_{N}$, and the black constraint of
$\Pi^{\prime}$ is $C_{E}$. Observe that, while $\Pi$ and $\Pi^{\prime}$ are
syntactically the same, an algorithm for $\Pi$ is designed for working on a
tree with no $2$-coloring given, and it needs to assign an output label to
each node-edge pair, while an algorithm for $\Pi^{\prime}$ is designed for
working on a tree that is properly $2$-colored and where all black nodes have
degree $2$, and it needs to assign an output label to each edge.

We first show that, given an algorithm $A$ for solving $\Pi$ with node-
averaged complexity $T$, we can design an algorithm $A^{\prime}$ for solving
$\Pi^{\prime}$ with node-averaged complexity $O(T)$. The algorithm
$A^{\prime}$ works as follows. White nodes simulate the execution of $A$,
while black nodes relay messages that are exchanged between white nodes. This
algorithm clearly solves $\Pi^{\prime}$. Each white node spends exactly twice
the running time of $A$, since each round of $A$ is simulated with $2$ rounds
of $A^{\prime}$ (it takes $2$ rounds for white nodes to exchange messages).
Observe that black nodes, in order to know their output, need to wait that the
two incident white neighbors terminate. Hence, we can charge their running
time to their slowest neighbor. Since each node is charged at most
$\Delta=O(1)$ times, then we obtain that $A^{\prime}$ has node-averaged
complexity $O(T)$.

We now show that, given an algorithm $A^{\prime}$ for solving $\Pi^{\prime}$
with node-averaged complexity $T$, we can design an algorithm $A$ for solving
$\Pi$ with node-averaged complexity $O(T)$. The algorithm $A$ is defined as
follows. Each edge of the tree is assigned to one incident node, arbitrarily.
In the algorithm $A$, the nodes pretend to be white nodes, and simulate the
execution of $A^{\prime}$. Moreover, the nodes simulate, for each incident
edge assigned to them, the execution of a black node, that is connected to the
two nodes incident to the edge. This algorithm clearly solves $\Pi$, and its
running time can be bounded as follows. The running time of each node is
charged to its longest running simulated (black or white) node. Observe that
each simulated node is charged at most once, and that the sum of the running
times of the simulated nodes that have been charged at least once is an upper
bound on the sum of the running times in $A$. This amount is at most $n\cdot
T$, where $n$ is the size of the simulated graph. Since the number of nodes in
the real graph and in the simulated one is asymptotically the same, then we
obtain that the node-averaged complexity of $A$ is at most $O(T)$. ∎

By combining Lemma 66 and Lemma 67 we obtain that focusing on LCLs in the
black-white formalism is not a restriction, and that our results apply to
standard LCLs as well. In particular, we obtain the following.

######  Lemma 68.

For any LCL problem $\Pi$ on trees with checkability radius $r$ and node-
averaged complexity $T$ we can define an LCL $\Pi^{\prime}$ in the black-white
formalism with node-averaged complexity $\Theta(T)$.