Classification of Local Optimization Problems in Directed Cycles

Boudier, Thomas; Kuhn, Fabian; Modanese, Augusto; Stimpert, Ronja; Suomela, Jukka

doi:10.4230/LIPIcs.ICALP.2026.42

Classification of Local Optimization Problems in Directed Cycles

Thomas Boudier

Gran Sasso Science Institute, L’Aquila, Italy Fabian Kuhn

University of Freiburg, Germany Augusto Modanese

CISPA Helmholtz Center for Information Security, Saarbrücken, Germany Ronja Stimpert

Aalto University, Espoo, Finland Jukka Suomela

Aalto University, Espoo, Finland

Abstract

We present a complete classification of the distributed computational complexity of local optimization problems in directed cycles for both the deterministic and the randomized LOCAL model. We show that for any local optimization problem $\Pi$ (that can be of the form min-sum, max-sum, min-max, or max-min, for any local cost or utility function over some finite alphabet), and for any constant approximation ratio $\alpha$ , the task of finding an $\alpha$ -approximation of $\Pi$ in directed cycles has one of the following complexities:

1.

$O(1)$ rounds in deterministic LOCAL, $O(1)$ rounds in randomized LOCAL,
2.

$\Theta(\log^{*}n)$ rounds in deterministic LOCAL, $O(1)$ rounds in randomized LOCAL,
3.

$\Theta(\log^{*}n)$ rounds in deterministic LOCAL, $\Theta(\log^{*}n)$ rounds in randomized LOCAL,
4.

$\Theta(n)$ rounds in deterministic LOCAL, $\Theta(n)$ rounds in randomized LOCAL.

Moreover, for any given $\Pi$ and $\alpha$ , we can determine the complexity class automatically, with an efficient (centralized, sequential) meta-algorithm, and we can also efficiently synthesize an asymptotically optimal distributed algorithm.

Before this work, similar results were only known for local search problems (e.g., locally checkable labeling problems). The family of local optimization problems is a strict generalization of local search problems, and it contains numerous commonly studied distributed tasks, such as the problems of finding approximations of the maximum independent set, minimum vertex cover, minimum dominating set, and minimum vertex coloring.

Keywords and phrases:

LOCAL model, optimization, cycles, meta-algorithms

Category:

Track A: Algorithms, Complexity and Games

Copyright and License:

© Thomas Boudier, Fabian Kuhn, Augusto Modanese, Ronja Stimpert, and
Jukka Suomela; licensed under Creative Commons License CC-BY 4.0

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Distributed algorithms

Related Version:

Full Version: https://arxiv.org/abs/2602.13046 [6]

Acknowledgements:

This project was initiated at the Research Workshop on Distributed Algorithms (RW-DIST 2025) in Freiburg, Germany; we would like to thank all workshop participants and organizers for inspiring discussions, and the anonymous reviewers for their helpful feedback on this paper. Most of this work was done while A.M. was affiliated with Aalto University.

Funding:

This work was supported in part by the Research Council of Finland, Grant 359104, and by the Quantum Doctoral Education Pilot, the Ministry of Education and Culture, decision VN/3137/2024-OKM-4.

DOI:

10.4230/LIPIcs.ICALP.2026.42

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

In this work we study distributed algorithms for local optimization problems – these include a wide range of familiar graph optimization problems such as maximum independent set, minimum vertex cover, minimum dominating set, and minimum vertex coloring. We show that in directed cycles, essentially all questions about the existence of distributed algorithms for local optimization problems can be answered in a mechanical and efficient manner. We give a meta-algorithm that answers the following questions, for any given local optimization problem $\Pi$ and any given constant approximation factor $\alpha$ :

1.

How fast can we find an $\alpha$ -approximation of $\Pi$ in the deterministic $\operatorname{\mathsf{LOCAL}}$ model?
2.

How fast can we find an $\alpha$ -approximation of $\Pi$ in the randomized $\operatorname{\mathsf{LOCAL}}$ model?

1.1 Broader Context

There is a long line of prior work that has studied local search problems, and in particular locally checkable labeling problems or LCLs; these are problems where the task is merely to satisfy all local constraints, i.e., the task is to find a feasible solution that does not need to be optimal in any sense. Familiar examples include the problems of finding a maximal independent set, or a valid coloring with $\Delta+1$ colors in a graph of maximum degree $\Delta$ .

While a lot of early work focused on specific concrete examples of such tasks, e.g., exactly what is the distributed complexity of finding a $3$ -coloring of a cycle [10, 20], Naor and Stockmeyer [22] initiated the study of meta-computational questions in this context: for any given local search problem $\Pi$ , can we systematically determine what the distributed computational complexity of $\Pi$ is?

It turns out that such questions are in general undecidable, already in the case of seemingly simple graph classes such as 2-dimensional grids [22, 7]. However, in graph families such as cycles, paths, and trees many such questions are decidable [9, 3, 4, 2]. Furthermore, while such questions are computationally hard if we have input labels [2], many of these questions can be solved efficiently (in time that is polynomial in the size of the description of problem $\Pi$ ) in the case of unlabeled graphs [9, 3].

In particular, if we look at LCL problems on unlabeled directed cycles, they are very well understood: the round complexity of any such problem is $O(1)$ , $\Theta(\log^{*}n)$ , or $\Theta(n)$ in all of our usual models of distributed computing (deterministic $\operatorname{\mathsf{LOCAL}}$ , randomized $\operatorname{\mathsf{LOCAL}}$ , deterministic $\operatorname{\mathsf{CONGEST}}$ , and randomized $\operatorname{\mathsf{CONGEST}}$ ), and there is a computer program that automatically finds out the complexity class for any given problem [24].

However, many problems that have been studied in the field of distributed graph algorithms are local optimization problems, e.g., [18, 11, 14, 13, 19, 17, 16], and much less is currently known about them. There is a large collection of isolated examples that apply to specific problems, but there is no complete classification of possible distributed round complexities of local optimization problems, and there is no meta-algorithm that is able to automatically determine the complexity of a given problem.

Furthermore, what makes the question particularly intriguing is that it is known that the complexity landscape has to be fundamentally different, already in the simplest case of unlabeled directed cycles. To see this, consider the problem of finding a $1.1$ -approximation of a minimum dominating set in cycles. Thanks to [11], it is known that in the deterministic $\operatorname{\mathsf{LOCAL}}$ model, the complexity of this problem is $\Theta(\log^{*}n)$ rounds, while in the randomized $\operatorname{\mathsf{LOCAL}}$ model, the complexity is $O(1)$ rounds. The same never happens with any LCL problem: for them, $O(1)$ rounds in randomized $\operatorname{\mathsf{LOCAL}}$ always implies $O(1)$ rounds in deterministic $\operatorname{\mathsf{LOCAL}}$ [8, 22].

Hence we have three questions that we aim to answer in this work:

1.

What is the right framework for formalizing and representing local optimization problems (analogous to LCL problems in the context of search problems)?
2.

What does the complexity landscape look like for local optimization, especially when we compare deterministic $\operatorname{\mathsf{LOCAL}}$ with randomized $\operatorname{\mathsf{LOCAL}}$ ?
3.

Can we design a meta-algorithm that automatically determines the complexity class for any given local optimization problem and any given approximation ratio?

1.2 Formalism

In this work, we look at the simplest nontrivial case: local optimization problems in directed cycles. Let us first recall how we can specify LCL problems in this setting: There is some finite set of output labels $\Gamma$ and verification distance $r$ , and we specify which $(r+1)$ -tuples of output labels are valid. For example, for the task of $3$ -coloring, we have $\Gamma=\{1,2,3\}$ , and we can select $r=1$ , and the set of valid tuples of output labels is $\{12,13,21,23,31,32\}$ . A feasible solution is a labeling $s\colon V\to\Gamma$ that is everywhere locally valid: for each node $v$ , the sequence of output labels $s(N_{r}(v))$ formed by $v$ and its $r$ successors is a valid tuple.

$\blacktriangleright$ Remark.

In cycles, it does not really matter whether we look at $v$ and its $r$ successors, or $v$ and its $r$ predecessors, or $v$ and its radius- $r/2$ symmetric neighborhood. In this work we follow the convention that a problem is defined in terms of $r$ successors.

In local optimization problems we keep the same basic setup, but now we associate a value $c(x)$ with each valid $(r+1)$ -tuple $x$ . This way, each labeling $s$ associates a local value $c(s(N_{r}(v)))$ with each node (we will use the terms cost or utility as appropriate to refer to the value, depending on the problem). The optimization task is one of the following, combining an objective function $\operatorname*{obj}\in\{\max,\min\}$ and an aggregation function $\operatorname*{aggr}\in\{\max,\min,\sum\}$ :

1.

$\max\min$ : maximize the minimum of local values,
2.

$\max\sum$ : maximize the sum of local values,
3.

$\min\max$ : minimize the maximum of local values,
4.

$\min\sum$ : minimize the sum of local values.

We will use the value $\bot$ to indicate forbidden label combinations (which can also be interpreted as e.g. infinite cost). We are interested in approximations, and we follow the convention that approximation ratio $\alpha$ is always at least $1$ , so e.g. a $2$ -approximation for a minimization problem is a feasible solution with total cost at most twice the optimum, and a $2$ -approximation for a maximization problem is a feasible solution with total utility at least half the optimum.

1.3 Examples of Problems

The following examples will hopefully clarify the formalism, and also demonstrate that it is broadly applicable. We will start with familiar, classic graph optimization problems.

Example 1.1 (maximum independent set).

The maximum independent set problem can be encoded as follows, with $1$ indicating nodes that form the independent set:

$\blacksquare$

$\Gamma=\{0,1\}$ , $r=1$ , $\operatorname*{obj}=\max$ , $\operatorname*{aggr}=\sum$ ,
$\blacksquare$

$c(00)=0$ , $c(01)=0$ , $c(10)=1$ , $c(11)=\bot$ .

Here any valid independent set has a nonnegative total value, and the value is equal to the size of the independent set.

Example 1.2 (minimum dominating set).

The minimum dominating set problem can be encoded as follows:

$\blacksquare$

$\Gamma=\{0,1\}$ , $r=2$ , $\operatorname*{obj}=\min$ , $\operatorname*{aggr}=\sum$ ,
$\blacksquare$

$c(000)=\bot$ , $c(001)=0$ , $c(010)=0$ , $c(011)=0$ ,
$c(100)=1$ , $c(101)=1$ , $c(110)=1$ , $c(111)=1$ .

Example 1.3 (minimum vertex coloring).

To encode the minimum vertex coloring problem, we can use e.g. the following formulation:

$\blacksquare$

$\Gamma=\{1,2,3\}$ , $r=1$ , $\operatorname*{obj}=\min$ , $\operatorname*{aggr}=\max$ ,
$\blacksquare$

$c(ij)=i$ if $i\neq j$ , $c(ii)=\bot$ .

Here for example a valid $2$ -coloring (using only colors $1$ and $2$ ) has total cost $2$ , and a valid $3$ -coloring has total cost $3$ .

Example 1.4 (maximum domatic partition).

Let us now look at a slightly more interesting example: domatic partition. In this problem, the task is to partition the set of nodes into as many disjoint dominating sets as possible; in a cycle we can have at most $3$ such sets. While more clever ad-hoc encodings are possible, we will use the following approach that generalizes to a wide range of similar problems. We use labels of the form $x_{i}$ , where $i$ indicates that we claim to have a solution with exactly $i$ dominating sets, and $x$ indicates that this node claims to be in a dominating set with label $x$ . We then need to ensure that nodes also agree on the number of dominating sets, and each dominating set is also valid. This will suffice:

$\blacksquare$

$\Gamma=\{a_{1},a_{2},b_{2},a_{3},b_{3},c_{3}\}$ , $r=2$ , $\operatorname*{obj}=\max$ , $\operatorname*{aggr}=\min$ ,
$\blacksquare$

$c(a_{1}a_{1}a_{1})=1$ ,
$\blacksquare$

$c(a_{2}a_{2}b_{2})=c(a_{2}b_{2}a_{2})=c(a_{2}b_{2}b_{2})=c(b_{2}a_{2}a_{2})=c(% b_{2}a_{2}b_{2})=c(b_{2}b_{2}a_{2})=2$ ,
$\blacksquare$

$c(a_{3}b_{3}c_{3})=c(b_{3}c_{3}a_{3})=c(c_{3}a_{3}b_{3})=c(a_{3}c_{3}b_{3})=c(% c_{3}b_{3}a_{3})=c(b_{3}a_{3}c_{3})=3$ ,
$\blacksquare$

$c(x)=\bot$ otherwise.

1.4 A Classification Example

So far we have seen examples of natural $\max\sum$ , $\min\sum$ , $\max\min$ , and $\min\max$ problems. We will introduce a somewhat artificial problem, which is engineered to illustrate many key phenomena in a single, concise package.

Example 1.5 (sloppy coloring).

In this problem, we can produce a proper $2$ -coloring with colors $\{\bullet,\circ\}$ , a proper $3$ -coloring with colors $\{1,2,3\}$ , or a somewhat sloppy $3$ -coloring with colors $\{a,b,c\}$ . The problem is defined as follows:

$\blacksquare$

$\Gamma=\{\bullet,\circ,1,2,3,a,b,c\}$ , $r=1$ , $\operatorname*{obj}=\min$ , $\operatorname*{aggr}=\sum$ ,
$\blacksquare$

$c(\bullet\circ)=c(\circ\bullet)=1$ ,
$\blacksquare$

$c(12)=c(21)=c(23)=c(32)=c(13)=c(31)=2$ ,
$\blacksquare$

$c(ab)=c(ba)=c(bc)=c(cb)=c(ac)=c(ca)=3$ ,
$\blacksquare$

$c(aa)=100$ ,
$\blacksquare$

$c(x)=\bot$ otherwise.

Let us try to gain a bit more intuition on the problem first. If we manage to produce a proper $2$ -coloring, the total cost in an $n$ -cycle is $n$ , and if we manage to produce a proper $3$ -coloring using labels $\{1,2,3\}$ , the total cost is $2n$ . If we resort to labels $\{a,b,c\}$ and produce a proper $3$ -coloring, the total cost is $3n$ . If a sublinear number of edges uses the color pair $a a$ , the total cost will be $3n+o(n)$ , and if we produce a trivial solution with all nodes colored $a$ , the total cost will be $100n$ .

Now the key question is this: given some constant $\alpha\geq 1$ , what is the distributed round complexity of finding an $\alpha$ -approximation of a sloppy coloring? It turns out that the complete answer in this case looks like this:

$\blacksquare$

For $1\leq\alpha<2$ , the complexity is $\Theta(n)$ in both the deterministic $\operatorname{\mathsf{LOCAL}}$ and randomized $\operatorname{\mathsf{LOCAL}}$ models. The optimal algorithm is a trivial brute-force algorithm that finds a $2$ -coloring if it exists, and otherwise produces a $3$ -coloring. There is no $o(n)$ -round algorithm for finding a $1.999$ -approximation or better.
$\blacksquare$

For $2\leq\alpha\leq 3$ , the complexity is $\Theta(\log^{*}n)$ in both the deterministic $\operatorname{\mathsf{LOCAL}}$ and randomized $\operatorname{\mathsf{LOCAL}}$ models. We can always produce a $3$ -coloring, using the Cole–Vishkin algorithm [10], and this is always a $2$ -approximation. There is no $o(\log^{*}n)$ -round deterministic or randomized algorithm for finding a $3$ -approximation or better.
$\blacksquare$

For $3<\alpha<100$ , the complexity is $\Theta(\log^{*}n)$ in the deterministic $\operatorname{\mathsf{LOCAL}}$ model but $O(1)$ in the randomized $\operatorname{\mathsf{LOCAL}}$ model. The randomized algorithm essentially finds a random ruling set to divide the cycle in segments. The algorithm uses color $a$ at the segment boundaries and fills in all sufficiently short segments with $b,c,b,c,\dotsc$ . Super-constant-length segments are rare, and there we can use the more costly solution $a,a,a,a,\dotsc$ . By adjusting the parameters, we can achieve approximation ratio $3+\epsilon$ for any constant $\epsilon>0$ with high probability (the worst case being that the input is an even cycle that could be $2$ -colored). There is no $o(\log^{*}n)$ -round deterministic algorithm for finding a $99.999$ -approximation or better.
$\blacksquare$

For $\alpha\geq 100$ , the complexity is $O(1)$ in both the deterministic $\operatorname{\mathsf{LOCAL}}$ and randomized $\operatorname{\mathsf{LOCAL}}$ models. The algorithm simply outputs $a$ everywhere.

As we will see, this turns out to be a well-representative problem: for any local optimization problem in our problem family, there are at most these four complexity classes, and the optimal algorithms are also essentially generalizations of the above four algorithms. We can automatically deduce all relevant $\alpha$ thresholds between the classes.

1.5 Contributions

We show that for any local optimization problem $\Pi$ (in the formalism of Section 1.2), and for any constant $\alpha$ , the task of finding an $\alpha$ -approximation of $\Pi$ in directed cycles has one of these complexities:

1.

$O(1)$ rounds in deterministic $\operatorname{\mathsf{LOCAL}}$ , $O(1)$ rounds in randomized $\operatorname{\mathsf{LOCAL}}$ ,
2.

$\Theta(\log^{*}n)$ rounds in deterministic $\operatorname{\mathsf{LOCAL}}$ , $O(1)$ rounds in randomized $\operatorname{\mathsf{LOCAL}}$ ,
3.

$\Theta(\log^{*}n)$ rounds in deterministic $\operatorname{\mathsf{LOCAL}}$ , $\Theta(\log^{*}n)$ rounds in randomized $\operatorname{\mathsf{LOCAL}}$ ,
4.

$\Theta(n)$ rounds in deterministic $\operatorname{\mathsf{LOCAL}}$ , $\Theta(n)$ rounds in randomized $\operatorname{\mathsf{LOCAL}}$ .

Moreover, for any given $\Pi$ and $\alpha$ , we can determine the complexity class automatically, with an efficient (centralized, sequential) meta-algorithm, and we can also efficiently synthesize an asymptotically optimal distributed algorithm. In particular, all local optimization problems similar to those in Sections 1.3 and 1.4 are now fully understood in the case of directed cycles.

One key consequence of our work is that increasing the running time from $\Theta(\log^{*}n)$ to, say, $\Theta(\log n)$ or $\Theta(\sqrt{n})$ does not give any constant advantage in the approximation ratio, for any local optimization problem in directed cycles. If we are interested in finding a $(1+1/n)$ -approximation, for example, then the situation is more complex, and indeed we might still obtain some sub-constant advantage by doing so. However, as we show, we will never be able to improve our approximation ratio from, say, $1.2345$ to $1.2344$ by such means. You will need to jump from $\Theta(\log^{*}n)$ rounds all the way to $\Theta(n)$ rounds for such an improvement.

We emphasize that the case of max-min and min-max problems can be handled by known techniques, as each fixed $\alpha$ essentially defines a sub-problem that is an LCL. The main novel part is $\min\sum$ and $\max\sum$ problems, which require genuinely new techniques and ideas. However, we wanted to give a unified formalization of all of these problems, and show that the same definitions and concepts indeed largely apply to both problem families.

1.6 Techniques

We take a three-step approach:

Step 1: Defining the problem parameters (Section 3).

We first define seven parameters ${\beta_{\operatorname{opt}}}$ , ${\beta_{\operatorname{flex}}}$ , ${\delta_{\operatorname{flex}}}$ , ${\beta_{\operatorname{coprime}}}$ , ${\beta_{\operatorname{gap}}}$ , ${\delta_{\operatorname{gap}}}$ , and ${\beta_{\operatorname{const}}}$ that capture essentially everything that we need to know about a given optimization problem $\Pi$ .

To do this, we define a node-weighted de Bruijn graph ${G_{\operatorname{dB}}}$ that captures the entire structure of $\Pi$ , including the values. The intuition is that for any input cycle $G$ , a feasible solution of $\Pi$ in $G$ corresponds to a closed walk in ${G_{\operatorname{dB}}}$ , with the same value. Then we proceed to define four subgraphs of ${G_{\operatorname{dB}}}$ :

1.

We let ${G_{\operatorname{opt}}}={G_{\operatorname{dB}}}$ . We define ${\beta_{\operatorname{opt}}}$ based on the cheapest closed walk in ${G_{\operatorname{opt}}}$ .
2.

We zoom into flexible components ${G_{\operatorname{flex}}}\subseteq{G_{\operatorname{opt}}}$ , in the spirit of [9]. In brief, a node $v$ of ${G_{\operatorname{dB}}}$ is $K$ -flexible if there are self-returning walks from $v$ back to $v$ of all possible lengths $K,K+1,K+2,\dotsc$ . A node is flexible if it is $K$ -flexible for some $K$ . It follows that in each strongly connected component either all or none of the nodes are flexible, and we say that a component is flexible if the nodes are flexible. We define parameters ${\beta_{\operatorname{flex}}}$ and ${\delta_{\operatorname{flex}}}$ based on the cheapest closed walks in ${G_{\operatorname{flex}}}$ .
3.

We zoom into flexible components with self-loops ${G_{\operatorname{gap}}}\subseteq{G_{\operatorname{flex}}}$ ; we simply take those flexible components that also contain nodes with a self-loop. We define parameters ${\beta_{\operatorname{gap}}}$ and ${\delta_{\operatorname{gap}}}$ based on the cheapest closed walks in ${G_{\operatorname{gap}}}$ .
4.

We form the subgraph that consists only of self-loops ${G_{\operatorname{const}}}\subseteq{G_{\operatorname{gap}}}$ . We define parameter ${\beta_{\operatorname{const}}}$ based on the cheapest closed walks (that is, cheapest self-loops) in ${G_{\operatorname{const}}}$ .

The above six parameters suffice for $\min\sum$ and $\max\sum$ problems. For max-min and min-max problems we also need to introduce a parameter ${\beta_{\operatorname{coprime}}}$ that, in brief, captures the cheapest pair of closed walks that have coprime lengths.

Table 1: All

\beta

values defined in Section 3 for the examples in Section 1.3. Missing values are not essential to capture the problem’s classification, regardless of whether the value can be obtained or not.

Example	${\beta_{\operatorname{opt}}}$	${\beta_{\operatorname{flex}}}$	${\delta_{\operatorname{flex}}}$	${\beta_{\operatorname{coprime}}}$	${\beta_{\operatorname{gap}}}$	${\delta_{\operatorname{gap}}}$	${\beta_{\operatorname{const}}}$
Example 1.1: max. independent set	$\frac{1}{2}$	$\frac{1}{2}$	true	–	$\frac{1}{2}$	true	$0$
Example 1.2: min. dominating set	$\frac{1}{3}$	$\frac{1}{3}$	true	–	$\frac{1}{3}$	true	$1$
Example 1.3: min. vertex coloring	$2$	–	false	$3$	$\bot$	false	$\bot$
Example 1.4: max. domatic partition	$3$	–	false	$2$	$1$	false	$1$
Example 1.5: sloppy coloring	$1$	$2$	false	–	$3$	true	$100$

Table 1 shows concrete examples of these parameter values for the examples from Section 1.3. We emphasize that these parameters have a purely graph-theoretic definition; their definitions do not make any references to e.g. a particular model of distributed computing. However, in step 3 we will see how these parameters connect with the task at hand.

Step 2: The problem parameters are efficiently computable (Section 4).

We show that given a description of any local optimization problem $\Pi$ , we can efficiently compute all necessary parameters out of ${\beta_{\operatorname{opt}}}$ , ${\beta_{\operatorname{flex}}}$ , ${\delta_{\operatorname{flex}}}$ , ${\beta_{\operatorname{coprime}}}$ , ${\beta_{\operatorname{gap}}}$ , ${\delta_{\operatorname{gap}}}$ , and ${\beta_{\operatorname{const}}}$ . In each case, we first construct the de Bruijn graph ${G_{\operatorname{dB}}}$ , which has size polynomial in the size of the problem description. Then we show that we can efficiently construct the relevant subgraph ( ${G_{\operatorname{opt}}},{G_{\operatorname{flex}}},{G_{\operatorname{gap}}},{G% _{\operatorname{const}}}$ ). Finally, we show that we can design an efficient graph algorithm for determining the corresponding parameter values based on the structure of the subgraph.

For example, to determine the value of ${\beta_{\operatorname{opt}}}$ for a $\min\sum$ problem, it is sufficient to find a cycle in ${G_{\operatorname{opt}}}={G_{\operatorname{dB}}}$ that minimizes the average cost; we show that all of this can indeed be done efficiently, largely relying on standard graph algorithms.

Determining e.g. ${\beta_{\operatorname{flex}}}$ and ${\delta_{\operatorname{flex}}}$ is more interesting, and there we will build on and extend prior work related to flexibility [9]. In brief, it is no longer sufficient to find a single cheap cycle, but we also need to find a pair of low-average-cost cycles with coprime lengths. We refer to Section 4 for the details of how all seven parameters can be determined efficiently.

Step 3: The problem parameters determine distributed complexity (Section 5).

Finally, we show that the complexity of any given problem for any approximation ratio $\alpha$ can be determined using parameters ${\beta_{\operatorname{opt}}}$ , ${\beta_{\operatorname{flex}}}$ , ${\delta_{\operatorname{flex}}}$ , ${\beta_{\operatorname{coprime}}}$ , ${\beta_{\operatorname{gap}}}$ , ${\delta_{\operatorname{gap}}}$ , and ${\beta_{\operatorname{const}}}$ . Furthermore, we can also automatically construct an asymptotically-fastest algorithm for any given $\alpha$ .

The intuition here is that ${\beta_{\operatorname{opt}}}$ provides a baseline against which we can compare. For example, for $\min\sum$ problems, for infinitely many values of $n$ , there exists a solution of total cost ${\beta_{\operatorname{opt}}}n$ , and for no value of $n$ we have cheaper solutions. So an average cost of ${\beta_{\operatorname{opt}}}$ per node represents the best-case scenario for the optimal solution. In particular, if we can find a solution of cost at most $\alpha{\beta_{\operatorname{opt}}}n$ for all $n$ , it will clearly be an $\alpha$ -approximation.

For a full classification, we will now need both upper bounds and matching lower bounds. Let us first consider upper bounds. It is perhaps easier to consider what we can do with a given time budget, using $\min\sum$ problems as an example:

1.

If we can use $O(n)$ rounds, we can brute-force an optimal solution, and hence trivially find a $1$ -approximation, regardless of the input size.
2.
If we can use only $O(\log^{*}n)$ rounds, we can use the following idea: find a sufficiently-sparse ruling set that divides the cycle into segments, so that the length of each segment is at least $A$ and at most $B$ for some appropriately-chosen constants $A$ and $B$ . Then we resort to the notion of flexibility: we put some fixed “flexible output sequence” $x$ at segment boundaries. Then we can follow a cheap closed walk from $x$ to $x$ in the de Bruijn graph ${G_{\operatorname{flex}}}$ to fill the gap between two such markers. There are two cases:
1. (a)
  
  There are two closed walks from $x$ to $x$ in ${G_{\operatorname{flex}}}$ that have coprime lengths and that have average cost exactly ${\beta_{\operatorname{flex}}}$ . Then by using a combination of such walks we can fill in gaps so that the total cost of the solution is exactly ${\beta_{\operatorname{flex}}}n$ , and hence we can achieve an approximation ratio of $\alpha={\beta_{\operatorname{flex}}}/{\beta_{\operatorname{opt}}}$ .
2. (b)
  
  Otherwise we will occasionally use slightly more expensive fragments, but we can still achieve a total cost of ${\beta_{\operatorname{flex}}}n+o(n)$ , and hence approximation ratio $\alpha={\beta_{\operatorname{flex}}}/{\beta_{\operatorname{opt}}}+\epsilon$ for any constant $\epsilon>0$ .
3.

If we further restrict the running time to $O(1)$ rounds, but allow the use of randomness, we can use a faster but sloppier approach for dividing the cycle into segments by choosing a random ruling set. The key difference is that now we can no longer guarantee that all segments have length at most some constant $B$ , yet we need to be able to solve the problem in constant time. This is where we resort to self-loops in ${G_{\operatorname{gap}}}$ : in those (rare) segments that are too long, we simply fill in the middle part of the segment by following a self-loop, that is, we produce in those areas a constant solution. For example, in the maximum independent set problem this means that we may occasionally have long stretches of $0$ s in our output. By choosing the parameters appropriately, we can achieve a total cost of ${\beta_{\operatorname{gap}}}n+o(n)$ , and hence an approximation ratio of $\alpha={\beta_{\operatorname{gap}}}/{\beta_{\operatorname{opt}}}+\epsilon$ .
4.

Finally, if we must use an $O(1)$ -round deterministic algorithm, we will produce a constant output that corresponds to following the cheapest self-loop of ${G_{\operatorname{const}}}$ repeatedly, achieving a total cost of ${\beta_{\operatorname{const}}}n$ and hence approximation ratio of $\alpha={\beta_{\operatorname{const}}}/{\beta_{\operatorname{opt}}}$ .

Then we need to show that the above strategy is optimal: there are no other complexity classes, and for each class the above approximation ratios are the best possible. To give some spirit of the lower bounds, we for example reason as follows. Assume that we have an algorithm that runs in $o(n)$ rounds. Then if the algorithm succeeds in producing a valid solution for every instance, it cannot use output values outside ${G_{\operatorname{flex}}}$ . Hence the output of the algorithm forms a closed walk in ${G_{\operatorname{flex}}}$ . But such walks have an average cost at least ${\beta_{\operatorname{flex}}}$ , while the optimum might have an average cost of ${\beta_{\operatorname{opt}}}$ , and it follows that the algorithm cannot find an approximation better than $\alpha={\beta_{\operatorname{flex}}}/{\beta_{\operatorname{opt}}}$ .

The lower bounds get more technical in the $O(\log^{*}n)$ region. There we use Naor’s randomized version [21] of Linial’s lower bound [20] as well as the Ramsey-theoretic lower bound technique familiar from Czygrinow, Hanckowiak, and Wawrzyniak [11]. We refer to Section 5 for the details.

1.7 Full Classification

Tables 2 and 3 summarize how we can determine the exact complexity class for any given problem $\Pi$ and any given approximation ratio $\alpha$ . The classification is complete; there are matching upper and lower bounds for each case. Table 4 shows what is obtained from applying our method to the previous examples from Section 1.3.

Table 2: Scheme for inferring the complexity class from the problem parameters of

\sum

-LCLs. To determine the optimal complexity for a problem and a given

\alpha

, one scans the “sufficient condition” column until a line is matched. Notice that the bounds given are tight in the sense that, if a condition on the right is satisfied and none of those above it apply, then the complexity on the left is also a lower bound for the corresponding approximation problem. For example, if we have a min

\sum

problem where

\alpha{\beta_{\operatorname{opt}}}\geq{\beta_{\operatorname{gap}}}

and

{\delta_{\operatorname{gap}}}

is false but

\alpha{\beta_{\operatorname{opt}}}<{\beta_{\operatorname{const}}}

holds, then there is an

\Omega(\log^{*}n)

lower bound for deterministic

\operatorname{\mathsf{LOCAL}}

.

Complexity		Sufficient condition
det. $\operatorname{\mathsf{LOCAL}}$	rand. $\operatorname{\mathsf{LOCAL}}$	$\min\sum$	$\max\sum$
$O(1)$	$O(1)$	$\alpha{\beta_{\operatorname{opt}}}\geq{\beta_{\operatorname{const}}}$	$\frac{1}{\alpha}{\beta_{\operatorname{opt}}}\leq{\beta_{\operatorname{const}}}$
$\Theta(\log^{*}n)$	$O(1)$	$\alpha{\beta_{\operatorname{opt}}}\geq{\beta_{\operatorname{gap}}}$ and ${\delta_{\operatorname{gap}}}$ is false	$\frac{1}{\alpha}{\beta_{\operatorname{opt}}}\leq{\beta_{\operatorname{gap}}}$ and ${\delta_{\operatorname{gap}}}$ is false
		$\alpha{\beta_{\operatorname{opt}}}>{\beta_{\operatorname{gap}}}$ and ${\delta_{\operatorname{gap}}}$ is true	$\frac{1}{\alpha}{\beta_{\operatorname{opt}}}<{\beta_{\operatorname{gap}}}$ and ${\delta_{\operatorname{gap}}}$ is true
$\Theta(\log^{*}n)$	$\Theta(\log^{*}n)$	$\alpha{\beta_{\operatorname{opt}}}\geq{\beta_{\operatorname{flex}}}$ and ${\delta_{\operatorname{flex}}}$ is false	$\frac{1}{\alpha}{\beta_{\operatorname{opt}}}\leq{\beta_{\operatorname{flex}}}$ and ${\delta_{\operatorname{flex}}}$ is false
		$\alpha{\beta_{\operatorname{opt}}}>{\beta_{\operatorname{flex}}}$ and ${\delta_{\operatorname{flex}}}$ is true	$\frac{1}{\alpha}{\beta_{\operatorname{opt}}}<{\beta_{\operatorname{flex}}}$ and ${\delta_{\operatorname{flex}}}$ is true
$\Theta(n)$	$\Theta(n)$	$\alpha{\beta_{\operatorname{opt}}}<{\beta_{\operatorname{flex}}}$	$\frac{1}{\alpha}{\beta_{\operatorname{opt}}}>{\beta_{\operatorname{flex}}}$
unsolvable	unsolvable	${\beta_{\operatorname{flex}}}=\bot$	${\beta_{\operatorname{flex}}}=\bot$

Table 3: Scheme for deriving the complexity class from the problem parameters of

\min

-

\max

and

\max

-

\min

-LCLs. The same remarks regarding determining the complexity of a problem as in Table 2 apply. Notice that, unlike the case of

\sum

-LCLs, there is not the possibility of a deterministic

\Theta(\log^{*}n)

and randomized

O(1)

complexity class here.

Complexity		Sufficient condition
det. $\operatorname{\mathsf{LOCAL}}$	rand. $\operatorname{\mathsf{LOCAL}}$	$\min\max$	$\max\min$
$O(1)$	$O(1)$	$\alpha{\beta_{\operatorname{opt}}}\geq{\beta_{\operatorname{const}}}$	$\frac{1}{\alpha}{\beta_{\operatorname{opt}}}\leq{\beta_{\operatorname{const}}}$
$\Theta(\log^{*}n)$	$\Theta(\log^{*}n)$	$\alpha{\beta_{\operatorname{opt}}}\geq{\beta_{\operatorname{coprime}}}$	$\frac{1}{\alpha}{\beta_{\operatorname{opt}}}\leq{\beta_{\operatorname{coprime}}}$
$\Theta(n)$	$\Theta(n)$	$\alpha{\beta_{\operatorname{opt}}}<{\beta_{\operatorname{coprime}}}$	$\frac{1}{\alpha}{\beta_{\operatorname{opt}}}>{\beta_{\operatorname{coprime}}}$
unsolvable	unsolvable	${\beta_{\operatorname{coprime}}}=\bot$	${\beta_{\operatorname{coprime}}}=\bot$

Table 4: Complexity of computing an

\alpha

-approximation in the deterministic and randomized

\operatorname{\mathsf{LOCAL}}

models for each of our examples from Section 1.3.

			Complexity
Example	Range of $\alpha$	Strategy	det. $\operatorname{\mathsf{LOCAL}}$	rand. $\operatorname{\mathsf{LOCAL}}$
Example 1.1:	$1$	Optimal	$\Theta(n)$	$\Theta(n)$
max independent set	$(1,\infty)$	Constant fragment	$\Theta(\log^{*}n)$	$O(1)$
Example 1.2:	$1$	Optimal	$\Theta(n)$	$\Theta(n)$
min. dominating set	$(1,3)$	Constant fragment	$\Theta(\log^{*}n)$	$O(1)$
	$[3,\infty)$	Constant solution	$O(1)$	$O(1)$
Example 1.3:	$[1,\tfrac{3}{2})$	Optimal	$\Theta(n)$	$\Theta(n)$
min. vertex coloring	$[\tfrac{3}{2},\infty)$	Flexible	$\Theta(\log^{*}n)$	$\Theta(\log^{*}n)$
Example 1.4:	$[1,\tfrac{3}{2})$	Optimal	$\Theta(n)$	$\Theta(n)$
max. domatic partition	$[\tfrac{3}{2},3)$	Flexible	$\Theta(\log^{*}n)$	$\Theta(\log^{*}n)$
	$[3,\infty)$	Constant solution	$O(1)$	$O(1)$
Example 1.5:	$[1,2)$	Optimal	$\Theta(n)$	$\Theta(n)$
sloppy coloring	$[2,3]$	Flexible	$\Theta(\log^{*}n)$	$\Theta(\log^{*}n)$
	$(3,100)$	Constant fragment	$\Theta(\log^{*}n)$	$O(1)$
	$[100,\infty)$	Constant solution	$O(1)$	$O(1)$

1.8 Future Directions and Open Questions

Our results are easy to adapt to weaker models: the results generalize essentially verbatim also to the $\operatorname{\mathsf{CONGEST}}$ model [23], and they are easy to adapt to the port-numbering model, where we essentially lose the deterministic $\Theta(\log^{*}n)$ class. However, generalizing the results to stronger classes leads to interesting open questions. One obvious candidate is the quantum- $\operatorname{\mathsf{LOCAL}}$ model; however, whether symmetry-breaking problems require $\Omega(\log^{*}n)$ rounds in quantum- $\operatorname{\mathsf{LOCAL}}$ is a major open question [1], and until this is resolved, we cannot fully characterize local optimization problems in the quantum- $\operatorname{\mathsf{LOCAL}}$ model, either.

An orthogonal direction is generalizations of our questions to more diverse families of inputs. The first steps would be to generalize our results from directed cycles to undirected cycles, directed paths, and rooted trees. Already the case of undirected cycles leads to new technical challenges: constant-round deterministic algorithms for optimization problems in undirected cycles may achieve non-trivial approximations (consider e.g. the task of orienting the edges, and assigning a higher cost to sink nodes). We believe that by introducing notions analogous to mirror-flexibility from [9] to our setting, it is also possible to eventually classify all these cases.

We have not considered inputs, and as soon as we have inputs, the classification will be $\mathsf{PSPACE}$ -hard [2]. Whether it is nevertheless decidable for local optimization problems with inputs is yet another open question for future work.

2 Preliminaries

We denote the set of positive integers by $\mathbb{N}^{+}$ and $\mathbb{N}^{+}\cup\{0\}$ by $\mathbb{N}_{0}^{+}$ . Similarly, $\mathbb{R}_{0}^{+}$ is the set of non-negative reals. We also write $[n]=\{1,\dots,n\}$ for the set of the first $n$ elements in $\mathbb{N}^{+}$ .

Our input graph is always a directed cycle $G=(V,E)$ . Without restriction, let us name the nodes of a directed cycle of length $n$ such that $V=\{v_{0},v_{1},\ldots,v_{n-1}\}$ and $(v_{i},v_{(i+1)\bmod n})\in E$ for $i\in\{0,\dots,n-1\}$ . The (one-way) neighborhood of radius $r\in\mathbb{N}_{0}^{+}$ of a node is a function $N_{r}\colon V\to V^{r+1}$ such that

N_{r}(v_{i})=(v_{i},v_{(i+1)\bmod n},\ldots,v_{(i+r)\bmod n}).

Hence the neighborhood of a node extends itself along a single direction of the cycle, namely following the orientation of the edges. We will use the one-way neighborhood to define the local costs incurred by every node; our computational model, however, allows communication in either direction (i.e., disregarding the orientation of the edges).

2.1 Locally Checkable Optimization Problems

A locally checkable optimization problem (opt-LCL) $\Pi$ on directed cycles is a tuple $\Pi=(\Gamma,r,c,\operatorname*{aggr},\operatorname*{obj})$ where:

$\blacksquare$

$\Gamma$ is a finite alphabet,
$\blacksquare$

$r\in\mathbb{N}_{0}^{+}$ is the (constant) radius,
$\blacksquare$

$c\colon\Gamma^{r+1}\to\mathbb{R}_{0}^{+}\cup\{\bot\}$ assigns every neighborhood a certain cost,
$\blacksquare$

$\operatorname*{aggr}\in\{\sum,\min,\max\}$ is an aggregation function,
$\blacksquare$

$\operatorname*{obj}\in\{\min,\max\}$ is an objective function.

The label $\bot$ is used to indicate neighborhoods that are not valid. In the following, such neighborhoods and their cost can be immediately disregarded. In order to distinguish different types of opt-LCLs we use shorthand such as $\operatorname*{obj}$ - $\operatorname*{aggr}$ -LCL (e.g., $\min$ - $\sum$ -LCL for an opt-LCL where $\operatorname*{obj}=\min$ and $\operatorname*{aggr}=\sum$ ), and we write $\sum$ -LCL for any opt-LCL where $\operatorname*{aggr}=\sum$ .

A solution $s$ on a directed cycle $G=(V,E)$ is a function $s:V\to\Gamma$ . For the neighborhood $N_{r}(v_{i})$ of a node $v_{i}$ , we define

s(N_{r}(v_{i}))=(s(v_{i}),s(v_{(i+1)\bmod n}),\ldots,s(v_{(i+r)\bmod n})).

We let $S_{n}$ be the solution space containing all solutions for a problem on a cycle with $n$ nodes. A solution $s$ to an opt-LCL $\Pi=(\Gamma,r,c,\operatorname*{aggr},\operatorname*{obj})$ on a directed cycle $G=(V,E)$ is said to be valid if and only if $c(s(N_{r}(v)))\neq\bot$ holds for every $v\in V$ .

The optimal cost of a problem $\Pi=(\Gamma,r,c,\operatorname*{aggr},\operatorname*{obj})$ on a directed cycle $G=(V,E)$ of length $n$ is a function

\operatorname*{OPT}(n)=\operatorname*{obj}_{s\in S_{n}}\operatorname*{aggr}_{v% \in V}c(s(N_{r}(v))).

Note that $\operatorname*{OPT}$ depends only on $n$ , since a directed cycle is determined by its length. A solution $s$ is said to be optimal for some $n$ if and only if

\operatorname*{aggr}_{v\in V}c(s(N_{r}(v)))=\operatorname*{OPT}(n).

For an opt-LCL $\Pi$ with $\operatorname*{obj}=\min$ , a solution of value $v$ in an $n$ -cycle is an $\alpha$ -approximation if $\alpha\cdot\operatorname*{OPT}(n)\geq v$ . For $\operatorname*{obj}=\max$ , the condition is that $\frac{1}{\alpha}\operatorname*{OPT}(n)\leq v$ . An algorithm is said to find an $\alpha$ -approximation for $\Pi$ if it finds an $\alpha$ -approximation for any $n$ .

2.2 The $\operatorname{\mathsf{LOCAL}}$ Model

We assume the usual distributed $\operatorname{\mathsf{LOCAL}}$ model of computation due to Linial [20]. The input graph $G$ is perceived as defining a distributed network where nodes are computers and edges are communication links. The orientation of an edge is interpreted as input information and does not constrain communication in any way (i.e., it is allowed to send messages in the opposite direction of an edge). Each node is assigned a unique identifier from the set $[n^{c}]$ , where $c>1$ is some constant of our choosing. Computation proceeds in rounds, where in each round a computer exchanges messages of unbounded size with its neighbors and executes a procedure where it decides whether to commit to an output or not and what to send on the next round of communication. We disregard time and space complexity of local computation and care only about the number of communication rounds required to solve the problem at hand. In this paper, our upper bounds give computable local procedures at every node whereas for the lower bounds we may as well assume an arbitrary procedure.

Whenever we address the randomized $\operatorname{\mathsf{LOCAL}}$ model, we say that an algorithm produces an $\alpha$ -approximation if, with high probability, the output is valid for the problem and additionally approximates the optimal solution within a factor of $\alpha$ . That is, with probability at most $\frac{1}{n}$ , the result is a labeling that is either invalid or does not satisfy the allowed approximation ratio.

3 Defining Problem Parameters

In this section, we define the seven parameters ${\beta_{\operatorname{opt}}}$ , ${\beta_{\operatorname{flex}}}$ , ${\beta_{\operatorname{coprime}}}$ , ${\delta_{\operatorname{flex}}}$ , ${\beta_{\operatorname{gap}}}$ , ${\delta_{\operatorname{gap}}}$ , and ${\beta_{\operatorname{const}}}$ that fully capture the complexity of producing approximations of an opt-LCL $\Pi$ . Before we can do this in Definitions 3.5, 3.6, and 3.7, we first introduce some technical tools which we also require later in Section 4.

The main technical tool that we employ to analyze an opt-LCL $\Pi$ is the de Bruijn graph associated with it. The values of the problem parameters for $\Pi$ all come from characteristics of certain walks in the de Bruijn graph associated with it.

Definition 3.1 (De Bruijn Graph).

Given an opt-LCL $\Pi=(\Gamma,r,c^{\prime},\operatorname*{aggr},\operatorname*{obj})$ , its de Bruijn graph is the digraph ${G_{\operatorname{dB}}}=({V_{\operatorname{dB}}},{A_{\operatorname{dB}}})$ where:

$\blacksquare$

The nodes in ${V_{\operatorname{dB}}}$ are all $(r+1)$ -tuples $(s_{1},\dots,s_{r+1})\in\Gamma^{r+1}$ fulfilling the condition $c^{\prime}((s_{1},\dots,s_{r+1}))\neq\bot$ .
$\blacksquare$

We have an edge from $(s_{1},\dots,s_{r+1})$ to $(t_{1},\dots,t_{r+1})$ if $t_{i}=s_{i+1}$ holds for every $i\in[r]$ .

Moreover we equip this graph with the cost function $c:{V_{\operatorname{dB}}}\to R(c^{\prime})$ , where $R(c^{\prime})$ is the range of $c^{\prime}$ . The function $c$ attributes to a particular neighborhood $N\in\Gamma^{r+1}$ its cost $c^{\prime}(N)$ . We denote by $\gamma\leq|\Gamma|^{r+1}$ the number of nodes in ${G_{\operatorname{dB}}}$ .

Figures 1(a), 1(b), 1(c), 1(d), and 2 show the de Bruijn graphs associated with the problems from Section 1.3.

(a) The de Bruijn graph of Example 1.1.

(b) The de Bruijn graph of Example 1.2.

(c) The de Bruijn graph of Example 1.3. On the left-hand side is the general structure of the graph. On the right-hand side is the subgraph relevant for calculating the values in Table 1.

(d) The de Bruijn graph of Example 1.4.

Figure 1: De Bruijn graphs for Examples 1.1, 1.2, 1.3, and 1.4, with the cost of each neighborhood in blue. Neighborhoods with cost

\bot

are not included in the De Bruijn graphs even if they occur in the respective problem.

Next we look at walks in the de Bruijn graph associated with $\Pi$ as well as the total cost incurred by following such walks.

Definition 3.2 ( $(u,v)$ -walk).

A sequence of nodes $W=w_{0},\dots,w_{k}$ with $\forall i,\,w_{i}\in{V_{\operatorname{dB}}}$ is a $(u,v)$ -walk if $w_{0}=u$ , $v=w_{k}$ and $\forall i,(w_{i},w_{i+1})$ is an arc of ${G_{\operatorname{dB}}}$ . When $u=v$ , we refer to $W$ as a closed walk, or, in particular, as a closed $v$ -walk.

Definition 3.3 (Cost of a walk).

Let $W=w_{0}\dots w_{k}$ be a walk with $k\geq 1$ . If $\operatorname*{aggr}=\sum$ , then $c(W)=\frac{1}{k}\sum_{i=1}^{k}c(w_{i})$ . Otherwise, $c(W)=\operatorname*{aggr}_{i\in[1,\dots,k]}c(w_{i})$ .

Note that we ignore the value of $c(w_{0})$ systematically to avoid counting some element twice when $W$ is a closed walk.

Finally, we define flexible nodes and components, which are relevant for flexible strategies.

Definition 3.4 (Flexible nodes and components).

A node $v$ of ${G_{\operatorname{dB}}}$ is flexible if there exists $K\in\mathbb{N}$ such that $\forall k\geq K$ , there exists a closed $v$ -walk of length exactly $k$ . We say in particular that $v$ is $K$ -flexible.

A strongly connected component $S\subseteq{V_{\operatorname{dB}}}$ of ${G_{\operatorname{dB}}}$ is a flexible component if there is a node $v\in S$ such that $v$ is flexible.

We are now ready to define the seven parameters ${\beta_{\operatorname{opt}}}$ , ${\beta_{\operatorname{flex}}}$ , ${\beta_{\operatorname{coprime}}}$ , ${\delta_{\operatorname{flex}}}$ , ${\beta_{\operatorname{gap}}}$ , ${\delta_{\operatorname{gap}}}$ , and ${\beta_{\operatorname{const}}}$ that capture the key properties of an opt-LCL $\Pi$ . Recall $\operatorname*{OPT}(n)$ denotes the value of an optimal solution for a cycle of $n$ nodes. Basically, we relate each of the $\beta_{a}$ values to the optimal solution in a certain subclass of the solution space. These subclasses are implicitly defined by taking appropriate subgraphs of the de Bruijn graph associated with $\Pi$ . Meanwhile, ${\delta_{\operatorname{flex}}}$ and ${\delta_{\operatorname{gap}}}$ are Boolean values that depend on certain specific properties of $\Pi$ .

Definition 3.5 ( ${G_{\operatorname{opt}}}$ , ${G_{\operatorname{flex}}}$ , ${G_{\operatorname{gap}}}$ , ${G_{\operatorname{const}}}$ ).

Let ${G_{\operatorname{dB}}}$ be the de Bruijn graph associated with an opt-LCL. We define a set of (possibly empty) subgraphs $\mathcal{G}=\{{G_{\operatorname{opt}}},{G_{\operatorname{flex}}},{G_{% \operatorname{gap}}},{G_{\operatorname{const}}}\}$ for $\Pi$ as follows:

1.

${G_{\operatorname{opt}}}={G_{\operatorname{dB}}}$ .
2.

${G_{\operatorname{flex}}}\subseteq{G_{\operatorname{opt}}}$ containing only the flexible components of ${G_{\operatorname{opt}}}$ , excluding all edges between different components.
3.

${G_{\operatorname{gap}}}\subseteq{G_{\operatorname{flex}}}$ containing only components of ${G_{\operatorname{flex}}}$ that contain a self-loop.
4.

${G_{\operatorname{const}}}\subseteq{G_{\operatorname{gap}}}$ containing only nodes of ${G_{\operatorname{gap}}}$ that have a self-loop and their self-loops.

Definition 3.6 ( ${\beta_{\operatorname{opt}}}$ , ${\beta_{\operatorname{flex}}}$ , ${\beta_{\operatorname{gap}}}$ , ${\beta_{\operatorname{const}}}$ , ${\delta_{\operatorname{flex}}}$ , ${\delta_{\operatorname{gap}}}$ ).

Let $\Pi=(\Gamma,r,c^{\prime},\operatorname*{aggr},\operatorname*{obj})$ be an opt-LCL. For each $G_{a}\in\mathcal{G}$ , we define $\mathcal{C}(G_{a})$ as the set of cycles (including self-loops) in $G_{a}$ and the real-valued parameter

\beta_{a}=\operatorname*{obj}_{\begin{subarray}{c}C\in\mathcal{C}(G_{a})\end{% subarray}}c(C).

If $\mathcal{C}(G_{a})$ is empty, then $\beta_{a}=\bot$ . The parameters ${\delta_{\operatorname{flex}}}$ and ${\delta_{\operatorname{gap}}}$ are defined as follows:

1.

${\delta_{\operatorname{flex}}}$ is false if there are two closed walks $W_{1},W_{2}$ in ${G_{\operatorname{flex}}}$ of coprime lengths, sharing a node, so that $c(W_{1})=c(W_{2})={\beta_{\operatorname{flex}}}$ ; otherwise, we set ${\delta_{\operatorname{flex}}}$ to true.
2.

${\delta_{\operatorname{gap}}}$ is false if ${\beta_{\operatorname{gap}}}={\beta_{\operatorname{const}}}$ , and true otherwise.

As an example, for $\min$ - $\sum$ -LCLs we can connect $\beta_{a}$ with concrete solutions to $\Pi$ as follows:

1.

${\beta_{\operatorname{opt}}}$ is the best possible relative value that can be achieved infinitely often (i.e., asymptotically) by the optimum over all cycle lengths;
2.

${\beta_{\operatorname{flex}}}$ is the (again, asymptotically) worst such value;
3.

${\beta_{\operatorname{gap}}}$ is the best possible value for solutions that admit constant neighborhoods, that is, where a single, fixed label appears;
4.

${\beta_{\operatorname{const}}}$ is the best possible (relative) value for constant solutions, that is, where the same fixed label is used everywhere.

Figure 2 shows how to obtain the relevant $\beta$ and $\delta$ values for Example 1.5. Note that for $\sum$ -LCLs, if $k$ is the length of the cycle providing ${\beta_{\operatorname{opt}}}$ , then $n\bmod k=0$ implies $\operatorname*{OPT}(k)/k=\operatorname*{OPT}(n)/n={\beta_{\operatorname{opt}}}$ . In addition, for large $n$ , we have ${\beta_{\operatorname{opt}}}\cdot n\leq\operatorname*{OPT}(n)\leq{\beta_{% \operatorname{flex}}}n+O(1)$ . It is possible that ${\delta_{\operatorname{flex}}}$ is false and ${\beta_{\operatorname{flex}}}={\beta_{\operatorname{opt}}}$ .

Definition 3.7 ( ${\beta_{\operatorname{coprime}}}$ ).

To define ${\beta_{\operatorname{coprime}}}$ , we let $V_{\leq}(r)=\left\{v\in{V_{\operatorname{dB}}}\mid c(v)\leq r\right\}$ and $V_{\geq}(r)=\left\{v\in{V_{\operatorname{dB}}}\mid c(v)\geq r\right\}.$ Let $G_{\leq}(r)$ and $G_{\geq}(r)$ be the subgraphs of the de Bruijn graph ${G_{\operatorname{dB}}}$ induced by $V_{\leq}(r)$ and $V_{\geq}(r)$ , respectively. We then define ${\beta_{\operatorname{coprime}}}$ for $\min$ - $\max$ -LCLs and $\max$ - $\min$ -LCLs as follows:

$\blacksquare$

For $\min$ - $\max$ -LCLs, ${\beta_{\operatorname{coprime}}}$ is the smallest $r\in\mathbb{R}_{0}^{+}$ for which the graph $G_{\leq}(r)$ contains two closed walks of coprime lengths that have a node in common.
$\blacksquare$

For $\max$ - $\min$ -LCLs, ${\beta_{\operatorname{coprime}}}$ is the largest $r\in\mathbb{R}_{0}^{+}$ for which the graph $G_{\geq}(r)$ contains two closed walks of coprime lengths that have a node in common.

Figure 2: An example for obtaining

\beta

and

\delta

values from a de Bruijn graph

{G_{\operatorname{dB}}}

when considering Example 1.5, with the cost of each neighborhood in blue and the relevant subgraphs of

{G_{\operatorname{dB}}}

in green. After identifying these subgraphs one can obtain the

\beta

values by finding the cycles with the cheapest average cost in each subgraph. The edges of a selection of such cheapest cycles are shown in red. To illustrate why

{\delta_{\operatorname{flex}}}

is false, two cycles of the same cost are highlighted in

{G_{\operatorname{flex}}}\setminus{G_{\operatorname{gap}}}

; these cycles have coprime lengths. Since

{\beta_{\operatorname{gap}}}\neq{\beta_{\operatorname{const}}}

,

{\delta_{\operatorname{gap}}}

is true.

4 Problem Parameters Are Computable Efficiently

In this section, denote by ${G_{\operatorname{dB}}}$ the de Bruijn graph of the given opt-LCL. Recall that $\gamma$ is its number of nodes. Next we present the necessary result to prove that all seven problem parameters can be computed efficiently. Note that ${\beta_{\operatorname{gap}}}$ , ${\delta_{\operatorname{flex}}}$ and ${\delta_{\operatorname{gap}}}$ are only relevant to $\sum$ -LCLs, so we do not need to compute them otherwise.

Let $\mathcal{W}_{\operatorname{opt}}$ be the set of closed walks that are optimal regarding the objective function. In the event that $\mathcal{W}_{\operatorname{opt}}=\emptyset$ , it is impossible to form a closed walk in ${G_{\operatorname{dB}}}$ , and hence it is impossible to solve $\Pi$ . Hence we may assume $\mathcal{W}_{\operatorname{opt}}\neq\emptyset$ .

Lemma 4.1.

If $\mathcal{W}_{\operatorname{opt}}\neq\emptyset$ , there exists a closed walk in $\mathcal{W}_{\operatorname{opt}}$ of length at most $\gamma$ .

Proof.

Let $w\in\mathcal{W}_{\operatorname{opt}}$ be a closed $v$ -walk of length at least $\gamma+1$ . We prove that we can find a walk $w^{\prime}\in\mathcal{W}_{\operatorname{opt}}$ such that $|w^{\prime}|<|w|$ . We repeat this argument on $w^{\prime}$ until we eventually find a walk of length at most $\gamma$ .

As $|w|\geq\gamma+1$ , by the pigeonhole principle, either $v$ is visited three times or there exists some $v^{*}\neq v$ visited twice. In the first case, we split $w$ into two closed $v$ -walks at $v$ , $L_{1}$ and $L_{2}$ . Observe that both $L_{1}$ and $L_{2}$ have lengths in $[1,|w|-1]$ , and both have their cost equal to $c(w)$ , as otherwise $w\notin\mathcal{W}_{\operatorname{opt}}$ : If $c(L_{1})<c(w)$ (resp., $c(L_{1})>c(w)$ in the case of maximization), $w$ is no longer optimal. Moreover, if $c(L_{1})>c(w)$ (resp., $c(L_{1})<c(w)$ for maximization), then for $\operatorname*{aggr}=\sum$ the other subwalk $L_{2}$ must have better cost than $w$ , while for $\operatorname*{aggr}\in\{\min,\max\}$ this contradicts the definition of $c(w)$ as the aggregate over $w$ . Hence, both of them belong to $\mathcal{W}_{\operatorname{opt}}$ .

If there is some $v^{*}\neq v$ visited twice, the proof is quite similar. Split $w$ into three walks at $v^{*}$ : $L_{1}=v,\dots,v^{*}$ , $L_{2}=v^{*},\dots,v^{*}$ and $L_{3}=v^{*},\dots,v$ . Now consider the two closed walks $L_{1}+L_{3}$ and $L_{2}$ . Their lengths are in $[1,|w|-1]$ and they both must have the same cost as $w$ ; hence they belong to $\mathcal{W}_{\operatorname{opt}}$ . $\hfill\blacktriangleleft$

The definition of $\mathcal{W}_{\operatorname{opt}}$ suggests that the optimal elements of the de Bruijn graph are closed walks and not only simple cycles. In the next lemma we prove that we can actually think only about cycles:

Lemma 4.2.

If there is a closed walk $W$ of length at most $\gamma$ with cost $\beta$ in the de Bruijn graph then there is a cycle of length at most $\gamma$ with cost at least as good as $\beta$ in terms of the optimization function.

Proof.

If $W$ is a cycle, the proof is trivial. Otherwise, choose two occurrences of the same node in $W$ that split $W$ into two shorter closed walks $W_{1}$ and $W_{2}$ . One of $W_{1}$ and $W_{2}$ has cost at least as good as $W$ with respect to the objective function: for $\operatorname*{aggr}=\sum$ this follows from the fact that $c(W)$ is the weighted average of $c(W_{1})$ and $c(W_{2})$ , while for $\operatorname*{aggr}\in\{\min,\max\}$ it follows directly from the aggregate over the concatenation. Continue with such a shorter closed walk until the remaining closed walk is a cycle. $\hfill\blacktriangleleft$

In order to compute ${\beta_{\operatorname{flex}}}$ and ${\beta_{\operatorname{coprime}}}$ it is crucial to identify flexible nodes of the graph. To figure out if a given node is flexible we prove the following lemma:

Lemma 4.3.

Node $v$ is flexible if and only if $v$ belongs to two closed walks of coprime lengths.

Proof.

Let $A$ and $B$ be two closed $v$ -walks with $a=|A|$ and $b=|B|$ being coprime. By the Frobenius coin theorem, all integers at least $(a-1)(b-1)$ can be obtained by a nonnegative integer combination of $a$ and $b$ . Concatenating the corresponding copies of $A$ and $B$ therefore gives closed $v$ -walks of all sufficiently large lengths, hence $v$ is flexible.

Now let $v$ be a flexible node. Hence there exists $K>0$ such that for all $k\geq K$ , there exists a closed $v$ -walk of length exactly $k$ . Pick any $a\geq K$ and $b\geq K$ such that $a$ and $b$ are coprime. The corresponding closed $v$ -walks have coprime lengths. $\hfill\blacktriangleleft$

Figuring out the value of ${\beta_{\operatorname{flex}}}$ is in principle easy: for each connected component, we can compute the cost of the optimum cycle in that component, and test which components are flexible. Testing the flexibility of a component can be achieved by considering walks of length $O(\gamma)$ [9]. We then set ${\beta_{\operatorname{flex}}}$ accordingly.

The hard part of our work is to decide whether ${\delta_{\operatorname{flex}}}$ is false or not. Parameter ${\delta_{\operatorname{flex}}}$ would be false only if there are two closed walks of coprime lengths, sharing a vertex and of cost ${\beta_{\operatorname{flex}}}$ . We adapt the procedure for testing flexibility from [9] to take into account the cost function of the de Bruijn graph in the next two lemmas.

Definition 4.4.

If $\Pi$ is an $\operatorname*{obj}$ - $\sum$ -LCL, then $G_{{\beta_{\operatorname{flex}}}}=(V_{{\beta_{\operatorname{flex}}}},A_{{\beta% _{\operatorname{flex}}}})$ , where

	$\displaystyle V_{{\beta_{\operatorname{flex}}}}$	$\displaystyle:=\left\{\ v\in{V_{\operatorname{dB}}}\mid v\text{ belongs to a % closed walk of cost }{\beta_{\operatorname{flex}}}\right\},$
	$\displaystyle A_{{\beta_{\operatorname{flex}}}}$	$\displaystyle:=\{\ (u,v)\in{A_{\operatorname{dB}}}\mid\text{$(u,v)$ belongs to% a closed walk of cost ${\beta_{\operatorname{flex}}}$}\}.$

It would be reasonable to think that having very long walks might be good in order to optimize the cost of a solution. We prove in our next lemma that this is not the case: all the walks of $G_{\beta_{\operatorname{flex}}}$ have cost exactly ${\beta_{\operatorname{flex}}}$ , and hence the length of the walk does not matter. This lemma, coupled with the fact that testing flexibility can be done by considering walks of limited length will allow us to efficiently test whether ${\delta_{\operatorname{flex}}}$ is false or not. As ${\delta_{\operatorname{flex}}}$ is a parameter defined only for $\operatorname*{obj}$ - $\sum$ -LCLs, there is no analogous definition of $G_{\beta_{\operatorname{flex}}}$ for $\min$ - $\max$ -LCLs and $\max$ - $\min$ -LCLs.

Lemma 4.5.

Let $\Pi$ be an $\operatorname*{obj}$ - $\sum$ -LCL. Any closed walk in the graph $G_{\beta_{\operatorname{flex}}}$ has cost exactly ${\beta_{\operatorname{flex}}}$ .

Proof.

Define the shifted cost function $c_{\beta_{\operatorname{flex}}}\colon V_{\beta_{\operatorname{flex}}}\to% \mathbb{R}$ by $c_{\beta_{\operatorname{flex}}}(v)=c(v)-{\beta_{\operatorname{flex}}}$ . Call the cost of a walk $W$ computed using $c_{\beta_{\operatorname{flex}}}$ instead of $c$ the shifted cost of $W$ . It is clear that a walk of cost ${\beta_{\operatorname{flex}}}$ has shifted cost zero (as $k{\beta_{\operatorname{flex}}}=\sum_{i=1}^{k}c(w_{i})$ if and only if $0=\sum_{i=1}^{k}(c(w_{i})-{\beta_{\operatorname{flex}}})$ for $\operatorname*{obj}$ - $\sum$ -LCLs). Moreover, by definition of ${\beta_{\operatorname{flex}}}$ , all closed walks must have shifted cost at least $0$ if $\operatorname*{obj}=\min$ (resp. at most $0$ if $\operatorname*{obj}=\max$ ). For simplicity, we can imagine that $G_{\beta_{\operatorname{flex}}}$ is constructed by adding one by one a finite number of simple closed walks $W_{1},W_{2},\dots$ of shifted cost zero. (Note that we do not actually need to design an algorithm to build this sequence.)

We now prove the lemma by induction. Let $W$ be a closed walk of $G_{\beta_{\operatorname{flex}}}$ . Assume that $W$ exists solely on the graph spanned by $W_{1}$ . It is clear that $W_{1}$ being a simple closed walk, $W$ consists of one or multiple instances of $W_{1}$ and hence $c_{\beta_{\operatorname{flex}}}(W)=0$ .

Suppose now that for some $k\in\mathbb{N}$ , any closed walk on the graph spanned by $\bigcup_{i}^{k}W_{i}$ has shifted cost exactly zero. We want to prove that any closed walk $W$ on $\bigcup_{i}^{k+1}W_{i}$ has shifted cost exactly $0$ . We use the following notation to represent $W$ :

a_{1}^{1},\dots,a_{k_{1}}^{1}=b_{1}^{1},\dots,b_{\ell_{1}}^{1}=a_{1}^{2},\dots% ,a_{k_{2}}^{2},\dots,

where $a_{k_{i}}^{i}=b_{1}^{i}$ , $b_{\ell_{i}}^{i}=a_{1}^{i+1}$ and $b_{i}^{j}$ are nodes of $W_{k+1}$ , and $a_{i}^{j}$ are other nodes. The reader can refer to Figure 3 as a visual aid for the rest of the proof.

Consider a walk $W^{\prime}$ defined in the following way: it is built following $W$ but each time we reach a frontier node $a_{k_{i}}^{i}=b_{1}^{i}$ , we add a first segment going from $a_{k_{i}}^{i}$ to $a_{1}^{i+1}$ through nodes in $\bigcup_{j=1}^{k}W_{j}$ then a second segment going from $a_{1}^{i+1}=b_{\ell_{i}}^{i}$ to $b_{1}^{i}$ through nodes of $W_{k+1}$ . Then, $W^{\prime}$ resumes its visit of $W$ . Note that it is possible to reorient the way in which $W^{\prime}$ is travelled so that it can be seen as a visit of $\bigcup_{i}^{k+1}W_{i}$ , then when it reaches a frontier node $b_{1}^{i}$ , it may go through $W_{k+1}$ entirely, then resume its visit of $\bigcup_{i}^{k}W_{i}$ . Then it is clear that $c_{\beta_{\operatorname{flex}}}(W^{\prime})=0$ as it consists of multiple travels through $W_{k+1}$ and a walk on $\bigcup_{i}^{k}W_{i}$ . Also, we have $W\subseteq W^{\prime}$ . If we had $c_{\beta_{\operatorname{flex}}}(W)>0$ (resp., $c_{\beta_{\operatorname{flex}}}(W)<0$ ), then in some way $W^{\prime}$ would be compensating in some part of $W^{\prime}-W$ . However, $W^{\prime}-W$ consists of a collection of cycles of the form $b_{\ell_{i}}^{i}\dots b_{1}^{i}$ plus some segments going from $a_{k_{i}}^{i}$ to $a_{1}^{i+1}$ in $\bigcup_{i}^{k}W_{i}$ . If $c_{\beta_{\operatorname{flex}}}(W)>0$ (resp., $c_{\beta_{\operatorname{flex}}}(W)<0$ ), then one of those cycles would be negative (resp., positive) shifted cost, which is a contradiction with the definition of ${\beta_{\operatorname{flex}}}$ . Hence it follows that all closed walks on $\bigcup_{i}^{k+1}W_{i}$ have cost exactly ${\beta_{\operatorname{flex}}}$ . $\hfill\blacktriangleleft$

Figure 3: Illustration of the construction of

W^{\prime}

using

W

in Lemma 4.5. Each time

W

uses some part of

W_{k+1}

, we add at the end of it the unused part of

W_{k+1}

(the green upper part) and any path going from

a^{i}_{k_{i}}

to

a_{1}^{i+1}

in

\bigcup_{i}^{k}W_{i}

. This way it is clear that

W^{\prime}

consists of possibly multiple instances of

W_{k+1}

and some closed walk on

\bigcup_{i}^{k}W_{i}

, making the shifted cost of

W^{\prime}

necessarily

0

.

For testing if a digraph has flexible nodes it is sufficient to look at closed walks of lengths at most $2\gamma+1$ , as shown in [9]. We give a version of this result tailored to our needs in the full version of this paper [6]:

Lemma 4.6.

Let $H=(U,F)$ be a strongly connected digraph of $n$ vertices. If $H$ has flexible vertices, then there exists a node $v\in U$ and two closed walks $A^{\prime},B^{\prime}$ containing $v$ such that $|A^{\prime}|$ and $|B^{\prime}|$ are coprime and both have length $\leq 2n+1$ .

We can directly use this result to prove that in $G_{\leq}({\beta_{\operatorname{coprime}}})$ (resp. $G_{\geq}({\beta_{\operatorname{coprime}}})$ ) there are two closed walks of coprime lengths that share a vertex, have length at most $2\gamma+1$ , and have cost at most (resp. at least) ${\beta_{\operatorname{coprime}}}$ as all walks of $G_{\leq}({\beta_{\operatorname{coprime}}})$ (resp. $G_{\geq}({\beta_{\operatorname{coprime}}})$ ) must have cost at most (resp. at least) ${\beta_{\operatorname{coprime}}}$ . Thanks to Lemma 4.5, we know that all the walks of $G_{\beta_{\operatorname{flex}}}$ have cost exactly ${\beta_{\operatorname{flex}}}$ , so we can also apply the same result. Then we can test if there are two closed walks of coprime lengths sharing a vertex and having cost ${\beta_{\operatorname{flex}}}$ by only looking at walks of length at most $2\gamma+1$ ; hence deducing efficiently whether ${\delta_{\operatorname{flex}}}$ is false or not.

Lemma 4.7.

Let ${G_{\operatorname{dB}}}$ be the de Bruijn graph of a $\sum$ -LCL. If there are two closed walks of coprime lengths sharing a vertex and having cost ${\beta_{\operatorname{flex}}}$ in ${G_{\operatorname{dB}}}$ , then there are two such walks of length at most $2\gamma+1$ .

Proof.

Apply Lemma 4.6 to any strongly connected component of $G_{{\beta_{\operatorname{flex}}}}$ containing such a shared vertex, where $G_{{\beta_{\operatorname{flex}}}}$ is defined in Lemma 4.5, and note that those walks exist in $G_{{\beta_{\operatorname{flex}}}}$ if and only if they exist in ${G_{\operatorname{dB}}}$ . $\hfill\blacktriangleleft$

Lemma 4.8.

For any opt-LCL, if they exist, we can compute the values of ${\beta_{\operatorname{opt}}}$ , ${\beta_{\operatorname{flex}}}$ , ${\delta_{\operatorname{flex}}}$ , ${\beta_{\operatorname{coprime}}}$ , ${\beta_{\operatorname{gap}}}$ , ${\delta_{\operatorname{gap}}}$ , and ${\beta_{\operatorname{const}}}$ in time polynomial in $|\Gamma|$ .

Proof.

First observe that for any opt-LCL we have $r=O(1)$ and hence any algorithm running in time polynomial in $|\Gamma|$ runs in time polynomial in $\gamma=|\Gamma|^{r+1}$ .

Let us start by addressing the more complex case of $\sum$ -LCLs. We will use the following subroutine: For $s\in{V_{\operatorname{dB}}}$ , let $A(s,K)$ be the following process: if it exists, denote by $F(s,v,k)$ an optimal $(s,v)$ -walk of length exactly $k$ . Initialize as non-existing $F(s,v,0)$ for $v\neq s$ and $F(s,s,0)=\{s\}$ . For all $v\in{V_{\operatorname{dB}}}$ and $k\geq 0$ we can compute $F(s,v,k+1)$ using the formula

\arg\operatorname*{obj}_{u\in{V_{\operatorname{dB}}}\cap N^{-}(v)}\big(c(F(s,u% ,k)+v)\big),

where $N^{-}(v)$ represents the predecessors of $v$ . Repeat this process until $k=K$ . Then output the list of tuples $(k,F(s,s,k))$ for each value of $k$ for which $F(s,s,k)$ exists. Algorithm $A(s,K)$ computes an optimal closed walk containing $s$ of length $k$ , for each $k\leq K$ for which such a walk exists. It can return multiple elements (at most $K$ tuples).

When $K$ is polynomial in $\gamma$ , algorithm $A(s,K)$ is clearly also polynomial in $\gamma$ . We can then use it to obtain all the desired values:

$\blacksquare$

${\beta_{\operatorname{opt}}}$ : Run $A(s,\gamma)$ for all $s$ and then figure for which $s, k$ we have an optimal $c(F(s,s,k))$ . Correctness is ensured by Lemma 4.1. Naturally, this procedure will also detect cycles among the closed walks. Lemma 4.2 ensures that the value we find will belong to at least one cycle, meeting the definition of ${\beta_{\operatorname{opt}}}$ . The procedure takes polynomial time in $\gamma$ as we call $A(s,\gamma)$ only $\gamma$ times.
$\blacksquare$

${\beta_{\operatorname{flex}}}$ and ${\delta_{\operatorname{flex}}}$ : First, determine the set of strongly connected components of ${G_{\operatorname{dB}}}$ . For each component, flexibility can be determined by observing the output of $A(s,2\gamma+1)$ for all $s$ : if $s$ is flexible, then it must belong to two closed walks of coprime lengths (Lemma 4.3), and there must be two such walks of lengths at most $2\gamma+1$ (Lemma 4.6). Now, for nodes in flexible components, we can determine the value of ${\beta_{\operatorname{flex}}}$ by running $A(s,\gamma)$ for each $s$ in a flexible component and picking the component that has the best cycle. As for ${\delta_{\operatorname{flex}}}$ , it suffices to look at the output of $A(s,2\gamma+1)$ in the good component and check if there are two closed walks containing $s$ , of coprime lengths and cost ${\beta_{\operatorname{flex}}}$ . In short, all we have to do is to run $A(s,2\gamma+1)$ once for all nodes and all the information we need is in that output. Calling $A(s,2\gamma+1)$ for all $s$ is clearly polynomial in $\gamma$ and all further analysis of the output is also polynomial.
$\blacksquare$

${\beta_{\operatorname{gap}}}$ and ${\delta_{\operatorname{gap}}}$ : Identify flexible components as explained above, but limit the considered components further by requiring them to contain one node with a self-loop. This procedure is clearly polynomial in $\gamma$ and obtains ${\beta_{\operatorname{gap}}}$ . Let $S_{\operatorname{loop}}$ be the set of all nodes with a self-loop. Then, ${\delta_{\operatorname{gap}}}$ is false if and only if $S_{\operatorname{loop}}$ contains a node with a self-loop of cost ${\beta_{\operatorname{gap}}}$ .
$\blacksquare$

${\beta_{\operatorname{const}}}$ : Run $A(s,1)$ for every $s$ . If $A(s,1)$ is non-empty, take the walk of optimal value (depending on $\operatorname*{obj}$ ).

As for $\min$ - $\max$ -LCLs and $\max$ - $\min$ -LCLs, the procedure is much easier. Start by listing in $L$ all costs $c(s)$ for all nodes and sort $L$ in ascending order if $\operatorname*{obj}=\min$ (resp. descending order if $\operatorname*{obj}=\max$ ). Then, for all $\ell\in L$ , we can construct the graphs $G_{\leq}(\ell)$ and $G_{\geq}(\ell)$ in time polynomial in $\gamma$ . Now, do the following: For all $\ell\in L$ in ascending order (resp. descending order), do the same procedure as for $\sum$ -LCLs to determine ${\beta_{\operatorname{opt}}}$ . If the procedure fails (meaning we could not find a closed walk of length at most $\gamma$ ), continue through $L$ . The first time the procedure succeeds, we have found ${\beta_{\operatorname{opt}}}=\ell$ . When ${\beta_{\operatorname{opt}}}$ is found we can do a similar procedure to find ${\beta_{\operatorname{coprime}}}$ : build $G_{\leq}(\ell)$ (resp. $G_{\geq}(\ell)$ ) and run $A(s,2\gamma+1)$ for all $s$ . As for $\operatorname*{obj}$ - $\sum$ -LCLs, this fully determines which components are flexible. The first time a flexible component is found, we have ${\beta_{\operatorname{coprime}}}=\ell$ . We repeat the same idea to find ${\beta_{\operatorname{const}}}$ . Regarding the complexity, we can notice that all the procedures that were polynomial in $\gamma$ for $\sum$ -LCLs are called at most $|L|\leq\gamma$ times, hence the whole algorithm runs in time polynomial in $\gamma$ . $\hfill\blacktriangleleft$

5 Problem Parameters Determine Distributed Complexity

In this final section, we show that the complexity of any given opt-LCL for any approximation ratio $\alpha$ can be determined using the parameters from Section 3. We do this by showing a series of lower and upper bounds in both deterministic and randomized $\operatorname{\mathsf{LOCAL}}$ based on these parameters. The result of all these observations is that every opt-LCL falls into one of five different classes based on its optimal complexity. An overview of these classes, which we label from A down to E, is provided in Table 5.

Throughout the previous sections we had to take into account that minimization and maximization problems behave in distinct ways, for example when referring to costs. However, the results we describe in this section can be readily ported from one case to the other by simple methods such as flipping signs or inverting fractions in the relevant inequalities. For example, an inequality $\alpha{\beta_{\operatorname{opt}}}>{\beta_{\operatorname{flex}}}$ in the minimization case becomes $\alpha/{\beta_{\operatorname{opt}}}>1/{\beta_{\operatorname{flex}}}$ in the maximization one (since we are interested in $1/\alpha$ as a factor instead of $\alpha$ ). Then we can simply recast the quantities $1/{\beta_{\operatorname{opt}}}$ and $1/{\beta_{\operatorname{flex}}}$ , respectively, as, say, $\beta^{\prime}_{\operatorname{opt}}$ and $\beta^{\prime}_{\operatorname{flex}}$ and proceed with the same argument. For this reason, in the text below we handle only the case of minimization problems and skip any mention of maximization problems altogether.

Table 5: Any

\alpha

-approximation of an opt-LCL

\Pi

falls into one of these five complexity classes, depending on the structure of

\Pi

and the value of

\alpha

.

	Complexity
Class	deterministic $\operatorname{\mathsf{LOCAL}}$	randomized $\operatorname{\mathsf{LOCAL}}$
A	$O(1)$	$O(1)$
B	$\Theta(\log^{*}n)$	$O(1)$
C	$\Theta(\log^{*}n)$	$\Theta(\log^{*}n)$
D	$\Theta(n)$	$\Theta(n)$
E	unsolvable	unsolvable

5.1 Lower Bounds

First we address lower bound results that show that Table 5 is complete, that is, that there is no opt-LCL whose optimal complexity lies in-between any of the classes A–E. For the full proofs of these results, please refer to the full version of this paper [6].

Lemma 5.1.

Assume there is a randomized $\operatorname{\mathsf{LOCAL}}$ algorithm that finds an $\alpha$ -approximation of some $\sum$ -LCL $\Pi$ in $o(n)$ rounds. Then $\alpha{\beta_{\operatorname{opt}}}\geq{\beta_{\operatorname{flex}}}$ holds, where the inequality is strict if and only if ${\delta_{\operatorname{flex}}}$ is true.

Since randomized $\operatorname{\mathsf{LOCAL}}$ is stronger than deterministic $\operatorname{\mathsf{LOCAL}}$ , this directly implies a lower bound of $\Omega(n)$ for deterministic $\operatorname{\mathsf{LOCAL}}$ as well.

Lemma 5.2.

If there is a randomized $\operatorname{\mathsf{LOCAL}}$ algorithm that finds an $\alpha$ -approximation of some $\min$ - $\max$ -LCL $\Pi$ in $o(n)$ rounds, then $\alpha{\beta_{\operatorname{opt}}}\geq{\beta_{\operatorname{coprime}}}$ .

Lemma 5.3.

If an opt-LCL $\Pi$ can be $\alpha$ -approximated in $o(\log^{\ast}n)$ rounds in the randomized $\operatorname{\mathsf{LOCAL}}$ model, then $\alpha{\beta_{\operatorname{opt}}}\geq{\beta_{\operatorname{gap}}}$ . Additionally, if ${\delta_{\operatorname{gap}}}$ is true, then this inequality is strict.

The proof follows more or less directly from well-known results on symmetry breaking and, in particular, the classical $\Omega(\log^{\ast}n)$ lower bound for $3$ -coloring [21]. Note that this lower bound holds even when we are allowed to err, for instance, with probability $1/\Omega(\log n)$ (instead of $1/n$ as usual).

Lemma 5.4.

If an opt-LCL $\Pi$ can be $\alpha$ -approximated in $o(\log^{\ast}n)$ rounds in the deterministic $\operatorname{\mathsf{LOCAL}}$ model, then $\alpha{\beta_{\operatorname{opt}}}\geq{\beta_{\operatorname{const}}}$ .

Our proof follows a similar idea to that of [11] based on an application of Ramsey’s theorem. For a set $X$ and $k\in\mathbb{N}_{+}$ , let us write $\binom{X}{k}$ for the subsets of $X$ of size exactly $k$ . For $k,r,s\in\mathbb{N}^{+}$ where $k\geq s\geq 2$ , we let $R(k;r,s)$ denote the size of the smallest $n\in\mathbb{N}^{+}$ such that every $r$ -coloring $c\colon\binom{[n]}{s}\to[r]$ of subsets of size $s$ of $[n]$ admits a subset $Y\in\binom{[n]}{k}$ for which $c$ is monochromatic on $\binom{Y}{s}$ . Such a number always exists by (the finite version of) Ramsey’s theorem (see, e.g., [15]) and can be asymptotically upper-bounded [12] by a power tower of height $s$ . The core of the argument is that, in the $o(\log^{\ast}n)$ regime, we can use Ramsey’s theorem to pick identifiers that force the output of the deterministic $\operatorname{\mathsf{LOCAL}}$ algorithm to be constant almost everywhere (i.e., on all but $o(n)$ nodes).

5.2 Upper Bounds

Finally we show upper bound results, that is, how each of the classes of Table 5 corresponds to obtaining an approximation to a desired factor $\alpha$ .

Lemma 5.5.

If $\alpha{\beta_{\operatorname{opt}}}\geq{\beta_{\operatorname{const}}}$ holds for some opt-LCL $\Pi$ with $\operatorname*{obj}=\min$ , then the complexity class of an algorithm that finds an $\alpha$ -approximation of $\Pi$ is A.

Proof.

$\alpha{\beta_{\operatorname{opt}}}\geq{\beta_{\operatorname{const}}}$ implies there exists a constant solution that approximates the best possible solution sufficiently well for any $n$ , as there is a self-loop in the de Bruijn graph. An algorithm finding an $\alpha$ -approximation of $\Pi$ can output a constant solution in $O(1)$ rounds in deterministic $\operatorname{\mathsf{LOCAL}}$ and randomized $\operatorname{\mathsf{LOCAL}}$ . Together with Lemma 5.4 this concludes the proof. $\hfill\blacktriangleleft$

Lemma 5.6.

Suppose $\alpha{\beta_{\operatorname{opt}}}<{\beta_{\operatorname{const}}}$ for some $\min$ - $\sum$ -LCL $\Pi$ and additionally one of the following two conditions holds:

1.

$\alpha{\beta_{\operatorname{opt}}}\geq{\beta_{\operatorname{gap}}}$ and ${\delta_{\operatorname{gap}}}$ is false.
2.

$\alpha{\beta_{\operatorname{opt}}}>{\beta_{\operatorname{gap}}}$ and ${\delta_{\operatorname{gap}}}$ is true.

Then the complexity class of any algorithm finding an $\alpha$ -approximation of $\Pi$ is B.

Proof.

As the definitions of ${\beta_{\operatorname{gap}}}$ and ${\delta_{\operatorname{gap}}}$ are simply more extensive than ${\beta_{\operatorname{flex}}}$ and ${\delta_{\operatorname{flex}}}$ , for deterministic $\operatorname{\mathsf{LOCAL}}$ we can proceed as in Lemma 5.8. For randomized $\operatorname{\mathsf{LOCAL}}$ it is known that we can find a ruling set in $O(1)$ with high probability [5]. With a ruling set and $K$ , as in Lemma 5.8, constant sequences can be labeled. Any superconstant-length sequences can be labeled with the self-loop included in the definition of ${\beta_{\operatorname{gap}}}$ . With high probability the cycle will use the cost of the self-loop only rarely even if it is higher than ${\beta_{\operatorname{gap}}}$ , so it is negligible on sufficiently large instances. Together with Lemma 5.3 this concludes the proof. $\hfill\blacktriangleleft$

The connection between the definition of ${\beta_{\operatorname{const}}}$ and a solution of an opt-LCL in a directed cycle is comparatively easy to make. It is less obvious how the cheapest cycle in a flexible component is the deciding cost for finding labelings in complexity class C. Therefore we make a connection to Section 3 with Lemma 5.7 leading up to Lemma 5.8.

Lemma 5.7.

If ${\beta_{\operatorname{flex}}}\neq\bot$ holds for a $\min$ - $\sum$ -LCL $\Pi$ , then there exists $K_{0}\in\mathbb{N}_{+}$ such that, for every $K\geq K_{0}$ , the de Bruijn graph of $\Pi$ admits a closed walk $W$ of length $K$ for which $c(W)\leq{\beta_{\operatorname{flex}}}+o(1)$ .

Proof.

Since ${\beta_{\operatorname{flex}}}\neq\bot$ , there exists at least one cycle of ${G_{\operatorname{dB}}}$ through which ${\beta_{\operatorname{flex}}}$ can be obtained. Let $C$ be one of these cycles. Because $C$ is in a flexible component $S$ , there exists a $K^{\prime}_{0}$ such that for all $K^{\prime}\geq K^{\prime}_{0}$ we can find a closed walk $W^{\prime}$ of length $K^{\prime}$ starting and ending in a node belonging to $C$ . This is achieved by connecting two closed walks of coprime lengths in $S$ to $C$ . Now we compose a walk $W$ of length $K$ by finding a $K^{\prime}\in[K^{\prime}_{0},K^{\prime}_{0}+|C|-1]$ so that $K-K^{\prime}$ is a multiple of $|C|$ . The number of different walks we have to find to achieve this is clearly upper bounded by $|C|$ . For large $K$ , the cost contribution of $W^{\prime}$ is negligible compared to the cost contribution of the copies of $C$ , whose average cost is $c(C)={\beta_{\operatorname{flex}}}$ . Choosing $K_{0}$ large enough handles the worst of the finitely many possible walks $W^{\prime}$ , as their potential additional cost impact is $o(1)$ compared to the length $K$ . $\hfill\blacktriangleleft$

Lemma 5.8.

Suppose one of the following two conditions holds for some $\min$ - $\sum$ -LCL $\Pi$ :

1.

$\alpha{\beta_{\operatorname{opt}}}\geq{\beta_{\operatorname{flex}}}$ and ${\delta_{\operatorname{flex}}}$ is false.
2.

$\alpha{\beta_{\operatorname{opt}}}>{\beta_{\operatorname{flex}}}$ and ${\delta_{\operatorname{flex}}}$ is true.

Then the complexity class of any algorithm finding an $\alpha$ -approximation of $\Pi$ is C, assuming $\Pi$ does not belong to either class A or B.

Proof.

If the first condition holds, then ${\delta_{\operatorname{flex}}}$ is false, so there are two closed walks of coprime lengths sharing a node and having cost exactly ${\beta_{\operatorname{flex}}}$ . By the same Frobenius argument as in Lemma 4.3, concatenating these walks gives closed walks of cost exactly ${\beta_{\operatorname{flex}}}$ for all sufficiently large lengths. If the second condition holds, Lemma 5.7 lets us choose $K$ large enough so that the $o(1)$ term is small enough. In either case, there exists a constant $K$ for which any path of length $\geq K$ can be labeled so that the resulting solution approximates the best possible solution sufficiently well for any $n$ . A $3$ -coloring can be found in $\Theta(\log^{*}n)$ [10, 20]. Then this coloring can be used to find sequences of length at least $K$ which can then be labeled to produce a sufficient approximation in each sequence of the graph and therefore also in the whole graph. Together with Lemma 5.1 this concludes the proof. $\hfill\blacktriangleleft$

Lemma 5.9.

If $\alpha{\beta_{\operatorname{opt}}}\geq{\beta_{\operatorname{coprime}}}$ for some $\min$ - $\max$ -LCL $\Pi$ , the complexity class of any algorithm finding an $\alpha$ -approximation of $\Pi$ is C, assuming $\Pi$ does not belong to class A.

Proof.

The proof is almost the same as the proof concerning the first condition in Lemma 5.8. The existence of the constant $K$ for which any path of length $\geq K$ can be labeled according to requirements is here directly rooted in the definition of ${\beta_{\operatorname{coprime}}}$ . Together with Lemma 5.2 this concludes the proof. $\hfill\blacktriangleleft$

Lemma 5.10.

If ${\beta_{\operatorname{flex}}}=\bot$ for a $\min$ - $\sum$ -LCL $\Pi$ or ${\beta_{\operatorname{coprime}}}=\bot$ for a $\min$ - $\max$ -LCL $\Pi^{\prime}$ , then the opt-LCL has no general solution and its complexity class is E. If the $\alpha$ -approximation algorithm is not in any of the classes A, B, C or E, then it is in the class D.

Proof.

If the relevant parameter is $\bot$ , then the problem does not have a valid solution on all instances. Otherwise, we know that $\alpha{\beta_{\operatorname{opt}}}n<{\beta_{\operatorname{flex}}}n+O(1)$ ( $\alpha{\beta_{\operatorname{opt}}}<{\beta_{\operatorname{coprime}}}$ ) holds for infinitely many $n$ , so on certain instances the whole graph must be known to all nodes in order to obtain an $\alpha$ -approximation. $\hfill\blacktriangleleft$

6 Putting Things Together

To recap, given an opt-LCL $\Pi$ , Section 4 allows us to calculate the values of all parameters $\beta_{a}$ and $\delta_{a}$ in polynomial time, and given these parameters, Section 5 lets us find out what is the round complexity of finding an $\alpha$ -approximation of $\Pi$ in the deterministic $\operatorname{\mathsf{LOCAL}}$ and randomized $\operatorname{\mathsf{LOCAL}}$ models. We have:

Theorem 6.1.

Given an opt-LCL $\Pi$ on directed cycles and a constant $\alpha$ , we can in polynomial time determine the asymptotic round complexity of finding an $\alpha$ -approximation of $\Pi$ in the deterministic $\operatorname{\mathsf{LOCAL}}$ and randomized $\operatorname{\mathsf{LOCAL}}$ models.

References

[1] Amirreza Akbari, Xavier Coiteux-Roy, Francesco D’Amore, François Le Gall, Henrik Lievonen, Darya Melnyk, Augusto Modanese, Shreyas Pai, Marc-Olivier Renou, Václav Rozhon, and Jukka Suomela. Online locality meets distributed quantum computing. In Michal Koucký and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 1295–1306. ACM, 2025. doi:10.1145/3717823.3718211.
[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 Peter Robinson and Faith Ellen, editors, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 262–271. ACM, 2019. 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 Christian Scheideler, editor, 36th International Symposium on Distributed Computing, DISC 2022, October 25-27, 2022, Augusta, Georgia, USA, volume 246 of LIPIcs, pages 8:1–8:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.DISC.2022.8.
[4] Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, Jukka Suomela, and Aleksandr Tereshchenko. Locally checkable problems in rooted trees. Distributed Computing, 36(3):277–311, 2023. doi:10.1007/S00446-022-00435-9.
[5] Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, and Dennis Olivetti. Node and edge averaged complexities of local graph problems. In Alessia Milani and Philipp Woelfel, editors, PODC ’22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022, pages 4–14. ACM, 2022. doi:10.1145/3519270.3538419.
[6] Thomas Boudier, Fabian Kuhn, Augusto Modanese, Ronja Stimpert, and Jukka Suomela. Classification of local optimization problems in directed cycles. CoRR, abs/2602.13046, 2026. doi:10.48550/arXiv.2602.13046.
[7] 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 Elad Michael Schiller and Alexander A. Schwarzmann, editors, Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 101–110. ACM, 2017. doi:10.1145/3087801.3087833.
[8] Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An exponential separation between randomized and deterministic complexity in the LOCAL model. SIAM Journal on Computing, 48(1):122–143, 2019. doi:10.1137/17M1117537.
[9] Yi-Jun Chang, Jan Studený, and Jukka Suomela. Distributed graph problems through an automata-theoretic lens. Theoretical Computer Science, 951:113710, 2023. doi:10.1016/J.TCS.2023.113710.
[10] Richard Cole and Uzi Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control, 70(1):32–53, 1986. doi:10.1016/S0019-9958(86)80023-7.
[11] Andrzej Czygrinow, Michal Hanckowiak, and Wojciech Wawrzyniak. Fast distributed approximations in planar graphs. In Gadi Taubenfeld, editor, Distributed Computing, 22nd International Symposium, DISC 2008, Arcachon, France, September 22-24, 2008. Proceedings, volume 5218 of Lecture Notes in Computer Science, pages 78–92. Springer, 2008. doi:10.1007/978-3-540-87779-0_6.
[12] P. Erdős and R. Rado. Combinatorial theorems on classifications of subsets of a given set. Proceedings of the London Mathematical Society, s3-2(1):417–439, 1952. doi:10.1112/plms/s3-2.1.417.
[13] Mika Göös, Juho Hirvonen, and Jukka Suomela. Lower bounds for local approximation. Journal of the ACM, 60(5):39:1–39:23, 2013. doi:10.1145/2528405.
[14] Mika Göös and Jukka Suomela. No sublogarithmic-time approximation scheme for bipartite vertex cover. Distributed Computing, 27(6):435–443, 2014. doi:10.1007/S00446-013-0194-Z.
[15] Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer. Ramsey Theory. Wiley Series in Discrete Mathematics and Optimization. Wiley, second edition, 1991.
[16] David G. Harris. Distributed local approximation algorithms for maximum matching in graphs and hypergraphs. SIAM Journal on Computing, 49(4):711–746, 2020. doi:10.1137/19M1279241.
[17] Ozan Heydt, Simeon Kublenz, Patrice Ossona de Mendez, Sebastian Siebertz, and Alexandre Vigny. Distributed domination on sparse graph classes. European Journal of Combinatorics, 123:103773, 2025. doi:10.1016/J.EJC.2023.103773.
[18] Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local computation: Lower and upper bounds. Journal of the ACM, 63(2):17:1–17:44, 2016. doi:10.1145/2742012.
[19] Christoph Lenzen and Roger Wattenhofer. Leveraging Linial’s locality limit. In Gadi Taubenfeld, editor, Distributed Computing, 22nd International Symposium, DISC 2008, Arcachon, France, September 22-24, 2008. Proceedings, volume 5218 of Lecture Notes in Computer Science, pages 394–407. Springer, 2008. doi:10.1007/978-3-540-87779-0_27.
[20] Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193–201, 1992. doi:10.1137/0221015.
[21] Moni Naor. A lower bound on probabilistic algorithms for distributive ring coloring. SIAM Journal on Discrete Mathematics, 4(3):409–412, 1991. doi:10.1137/0404036.
[22] Moni Naor and Larry J. Stockmeyer. What can be computed locally? SIAM Journal on Computing, 24(6):1259–1277, 1995. doi:10.1137/S0097539793254571.
[23] David Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, 2000. doi:10.1137/1.9780898719772.
[24] Aleksandr Tereshchenko and Jan Studený. LCL classifier, 2021. URL: https://lcl-classifier.cs.aalto.fi.

[bib.bib1] [1] Amirreza Akbari, Xavier Coiteux-Roy, Francesco D’Amore, François Le Gall, Henrik Lievonen, Darya Melnyk, Augusto Modanese, Shreyas Pai, Marc-Olivier Renou, Václav Rozhon, and Jukka Suomela. Online locality meets distributed quantum computing. In Michal Koucký and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 1295–1306. ACM, 2025. doi:10.1145/3717823.3718211.

[bib.bib2] [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 Peter Robinson and Faith Ellen, editors, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 262–271. ACM, 2019. doi:10.1145/3293611.3331606.

[bib.bib3] [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 Christian Scheideler, editor, 36th International Symposium on Distributed Computing, DISC 2022, October 25-27, 2022, Augusta, Georgia, USA, volume 246 of LIPIcs, pages 8:1–8:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.DISC.2022.8.

[bib.bib4] [4] Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, Jukka Suomela, and Aleksandr Tereshchenko. Locally checkable problems in rooted trees. Distributed Computing, 36(3):277–311, 2023. doi:10.1007/S00446-022-00435-9.

[bib.bib5] [5] Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, and Dennis Olivetti. Node and edge averaged complexities of local graph problems. In Alessia Milani and Philipp Woelfel, editors, PODC ’22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022, pages 4–14. ACM, 2022. doi:10.1145/3519270.3538419.

[bib.bib6] [6] Thomas Boudier, Fabian Kuhn, Augusto Modanese, Ronja Stimpert, and Jukka Suomela. Classification of local optimization problems in directed cycles. CoRR, abs/2602.13046, 2026. doi:10.48550/arXiv.2602.13046.

[bib.bib7] [7] 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 Elad Michael Schiller and Alexander A. Schwarzmann, editors, Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 101–110. ACM, 2017. doi:10.1145/3087801.3087833.

[bib.bib8] [8] Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An exponential separation between randomized and deterministic complexity in the LOCAL model. SIAM Journal on Computing, 48(1):122–143, 2019. doi:10.1137/17M1117537.

[bib.bib9] [9] Yi-Jun Chang, Jan Studený, and Jukka Suomela. Distributed graph problems through an automata-theoretic lens. Theoretical Computer Science, 951:113710, 2023. doi:10.1016/J.TCS.2023.113710.

[bib.bib10] [10] Richard Cole and Uzi Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control, 70(1):32–53, 1986. doi:10.1016/S0019-9958(86)80023-7.

[bib.bib11] [11] Andrzej Czygrinow, Michal Hanckowiak, and Wojciech Wawrzyniak. Fast distributed approximations in planar graphs. In Gadi Taubenfeld, editor, Distributed Computing, 22nd International Symposium, DISC 2008, Arcachon, France, September 22-24, 2008. Proceedings, volume 5218 of Lecture Notes in Computer Science, pages 78–92. Springer, 2008. doi:10.1007/978-3-540-87779-0_6.

[bib.bib12] [12] P. Erdős and R. Rado. Combinatorial theorems on classifications of subsets of a given set. Proceedings of the London Mathematical Society, s3-2(1):417–439, 1952. doi:10.1112/plms/s3-2.1.417.

[bib.bib13] [13] Mika Göös, Juho Hirvonen, and Jukka Suomela. Lower bounds for local approximation. Journal of the ACM, 60(5):39:1–39:23, 2013. doi:10.1145/2528405.

[bib.bib14] [14] Mika Göös and Jukka Suomela. No sublogarithmic-time approximation scheme for bipartite vertex cover. Distributed Computing, 27(6):435–443, 2014. doi:10.1007/S00446-013-0194-Z.

[bib.bib15] [15] Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer. Ramsey Theory. Wiley Series in Discrete Mathematics and Optimization. Wiley, second edition, 1991.

[bib.bib16] [16] David G. Harris. Distributed local approximation algorithms for maximum matching in graphs and hypergraphs. SIAM Journal on Computing, 49(4):711–746, 2020. doi:10.1137/19M1279241.

[bib.bib17] [17] Ozan Heydt, Simeon Kublenz, Patrice Ossona de Mendez, Sebastian Siebertz, and Alexandre Vigny. Distributed domination on sparse graph classes. European Journal of Combinatorics, 123:103773, 2025. doi:10.1016/J.EJC.2023.103773.

[bib.bib18] [18] Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local computation: Lower and upper bounds. Journal of the ACM, 63(2):17:1–17:44, 2016. doi:10.1145/2742012.

[bib.bib19] [19] Christoph Lenzen and Roger Wattenhofer. Leveraging Linial’s locality limit. In Gadi Taubenfeld, editor, Distributed Computing, 22nd International Symposium, DISC 2008, Arcachon, France, September 22-24, 2008. Proceedings, volume 5218 of Lecture Notes in Computer Science, pages 394–407. Springer, 2008. doi:10.1007/978-3-540-87779-0_27.

[bib.bib20] [20] Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193–201, 1992. doi:10.1137/0221015.

[bib.bib21] [21] Moni Naor. A lower bound on probabilistic algorithms for distributive ring coloring. SIAM Journal on Discrete Mathematics, 4(3):409–412, 1991. doi:10.1137/0404036.

[bib.bib22] [22] Moni Naor and Larry J. Stockmeyer. What can be computed locally? SIAM Journal on Computing, 24(6):1259–1277, 1995. doi:10.1137/S0097539793254571.

[bib.bib23] [23] David Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, 2000. doi:10.1137/1.9780898719772.

[bib.bib24] [24] Aleksandr Tereshchenko and Jan Studený. LCL classifier, 2021. URL: https://lcl-classifier.cs.aalto.fi.

Classification of Local Optimization Problems in Directed Cycles

Abstract

Keywords and phrases:

Category:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Broader Context

1.2 Formalism

▶ Remark.

1.3 Examples of Problems

Example 1.1 (maximum independent set).

Example 1.2 (minimum dominating set).

Example 1.3 (minimum vertex coloring).

Example 1.4 (maximum domatic partition).

1.4 A Classification Example

Example 1.5 (sloppy coloring).

1.5 Contributions

1.6 Techniques

Step 1: Defining the problem parameters (Section 3).

Step 2: The problem parameters are efficiently computable (Section 4).

Step 3: The problem parameters determine distributed complexity (Section 5).

1.7 Full Classification

1.8 Future Directions and Open Questions

2 Preliminaries

2.1 Locally Checkable Optimization Problems

2.2 The 𝗟𝗢𝗖𝗔𝗟 Model

3 Defining Problem Parameters

Definition 3.1 (De Bruijn Graph).

Definition 3.2 ((u,v)-walk).

Definition 3.3 (Cost of a walk).

Definition 3.4 (Flexible nodes and components).

Definition 3.5 (Gopt, Gflex, Ggap, Gconst).

Definition 3.6 (βopt, βflex, βgap, βconst, δflex, δgap).

Definition 3.7 (βcoprime).

4 Problem Parameters Are Computable Efficiently

Lemma 4.1.

Proof.

Lemma 4.2.

Proof.

Lemma 4.3.

Proof.

Definition 4.4.

Lemma 4.5.

Proof.

Lemma 4.6.

Lemma 4.7.

Proof.

Lemma 4.8.

Proof.

5 Problem Parameters Determine Distributed Complexity

5.1 Lower Bounds

Lemma 5.1.

Lemma 5.2.

Lemma 5.3.

Lemma 5.4.

5.2 Upper Bounds

Lemma 5.5.

Proof.

Lemma 5.6.

Proof.

Lemma 5.7.

Proof.

Lemma 5.8.

Proof.

Lemma 5.9.

Proof.

Lemma 5.10.

Proof.

6 Putting Things Together

Theorem 6.1.

References

$\blacktriangleright$ Remark.

2.2 The $\operatorname{\mathsf{LOCAL}}$ Model

Definition 3.2 ( $(u,v)$ -walk).

Definition 3.5 ( ${G_{\operatorname{opt}}}$ , ${G_{\operatorname{flex}}}$ , ${G_{\operatorname{gap}}}$ , ${G_{\operatorname{const}}}$ ).

Definition 3.6 ( ${\beta_{\operatorname{opt}}}$ , ${\beta_{\operatorname{flex}}}$ , ${\beta_{\operatorname{gap}}}$ , ${\beta_{\operatorname{const}}}$ , ${\delta_{\operatorname{flex}}}$ , ${\delta_{\operatorname{gap}}}$ ).

Definition 3.7 ( ${\beta_{\operatorname{coprime}}}$ ).