Superlogarithmic Gap Result for LCLs on Trees in Quantum-LOCAL

Superlogarithmic Gap Result for LCLs on Trees in Quantum-LOCAL Francesco d’Amore · Gran Sasso Science Institute, Italy Henrik Lievonen · Aalto University, Espoo, Finland · CISPA Helmholtz Center for

arXiv:2608.16854v1 [cs.CC] 17 Aug 2026

Information Security, Saarbrücken, Germany

Abstract. We show that, on trees, any locally checkable labeling problem (LCL) Π that can be solved by an no(1) -dependent distribution can also be solved by an O(log n)-round deterministic LOCAL algorithm. The result is obtained through a rake-and-compress-style decomposition of the input tree, and local simulations of the bounded dependent distribution on the components of the decomposition. As a corollary to our result, any LCL problem on trees can either be solved by an O(log n) deterministic LOCAL algorithm, or requires nΩ(1) rounds to solve by a quantum-LOCAL algorithm. Acknowledgements. Francesco d’Amore was supported by Decreto MUR n. 47/2025, CUP D13C25000750001. This work was supported in part by the Research Council of Finland, Grants 363558. Most of this work was done while Henrik Lievonen was affiliated with Aalto University.

1

Introduction

The distributed computing community has recently made significant progress in understanding the role of quantum computation and communication in the context of distributed graph problems [16, 27–29], even with respect to locally checkable labeling (LCL) problems in the LOCAL model [1, 3, 21, 23]. LCL problems are problems whose solutions are easy to verify, but might be hard to find by a distributed algorithm. More precisely, an LCL problem can be specified by a finite list C of valid labeled neighborhoods of constant radius and of bounded degree, and a node can verify its local solution by simply inspecting is constant-radius neighborhood and checking whether it belongs to C [34]. Many classical distributed graph problems, such as vertex coloring, maximal independent set, maximal matching, sinkless orientation, etc., belong to this class: in essence, the class of LCL problems is wide enough to include many interesting natural graph problems but restrictive enough so that many results apply to the class as a whole – in fact, the complexity of LCL problems in the classical LOCAL model is nowadays well-understood [4,7,12,14,15,17,19,20,22,34,35], and we especially know when randomness helps (or does not help) in solving them [6, 11, 19, 20]. While general quantum advantage in the LOCAL model was already established in 2019 [30], the complexity landscape of LCL problems in the quantum-LOCAL model [26] is much less understood, with mostly negative results showing that quantum computation and communication cannot bring (much) advantage [1, 2, 10, 21, 23, 24, 26]. Only few positive results have been recently provided [3, 8], exhibiting artificially crafted LCL problems that can be solved faster in quantum-LOCAL than in classical LOCAL, which leave open whether natural LCL problems admit quantum advantage. On the negative side, it has been proved that for approximate graph coloring problems, quantum-LOCAL algorithms cannot be substantially faster than deterministic LOCAL algorithms [21], and that linear programming problems do not admit any quantum advantage with respect to deterministic algorithms [10]. More generally, there have been works showing general negative 1

results for LCL problems on specific graph families: It is known that on rooted trees, o(log log log n)round quantum algorithms for an LCL can be transformed into O(log⋆ n)-round deterministic LOCAL algorithms [1]. Moreover, Dhar et al. [24] proved the following statements: 1. On rooted regular trees, there is no possible quantum advantage unless the classical deterministic complexity is O(log⋆ n). 2. On rooted trees, a global problem (i.e., a problem with classical locality Ω(n)) cannot be solved in quantum-LOCAL with locality o(n). 3. On unrooted regular trees, if the deterministic complexity is ω(log n), then there cannot be any quantum advantage. 4. On unrooted trees, a global problem cannot be solved in quantum-LOCAL with locality o(n). The situation in trees is quite unsatisfactory, especially because most of the classification results for LCL problems in the classical LOCAL model are specific to the family of trees [17]. In this work, we make a step towards a better comprehension of the quantum complexity landscape on trees. We prove that, on unrooted trees, any LCL problem that can be solved by an no(1) -round quantum-LOCAL algorithm can also be solved by an O(log n)-round deterministic LOCAL algorithm. The same result trivially extends to the case of rooted trees, which was left open by [24]. We actually prove a stronger result: on unrooted trees, any LCL problem that can be solved by an no(1) -dependent distribution can also be solved by an O(log n)-round deterministic LOCAL algorithm. We recall that a T -dependent distribution is a probability distribution over the output labelings of the graph such that, for every two subsets of nodes A and B at distance at least T + 1, the random variables corresponding to the output labels of nodes in A and those in B are mutually independent. Note that a T -round quantum-LOCAL algorithm always produces a 2T -dependent distribution [1]: hence, negative results for T -dependent distributions also apply to quantum-LOCAL algorithms with locality ⌊T /2⌋.

2

Preliminary definitions

We present here informal definitions of the models of computation we use. We refer the reader to Appendix A for more formal definitions.

2.1

The models

We work in the LOCAL model of distributed computing: in this model, the computation proceeds in synchronous rounds, and in each round, each node can perform unlimited local computation and exchange messages of unbounded size with its neighbors. Nodes receive as input the size n of the graph, and they have unique O(log n)-bit identifiers (IDs) that are distinct from each other. In the randomized LOCAL model, as opposed to the deterministic LOCAL model, nodes also have access to private source of randomness, and the algorithm is allowed to fail with probability at most 1/nc for any given c > 0. In the quantum-LOCAL model, nodes can exchange an arbitrary number of qubits and perform arbitrary unitary transformations on their local quantum states: the output of a node is just the measurement outcome of its local quantum state, and the algorithm is allowed to fail with probability at most 1/nc for any given c > 0.

2

Finally, we also consider the bounded-dependence model [1], where we assign to each input graph a probability distribution over the output labelings, and we say that this assignment has locality T if the two following statements hold: 1. Independence property: For every input graph G, and any two subsets of nodes A and B at distance at least 2T + 1, the random variables corresponding to the output labels of nodes in A and those in B are mutually independent. In such case, we say that the distribution is 2T -dependent. 2. Non-signaling property: For every two input graphs G and G′ that are identical in the radius-T neighborhood of a subset of nodes A, the marginal distributions of the output labels of A are the same in both distributions. Again, in this model we require that the distribution solves the problem with probability at least 1 − 1/nc for any given c > 0. It holds that a T -round LOCAL algorithm (being it deterministic, randomized, or quantum) always produces a bounded-dependent distribution with locality T [1]. Hence, a lower bound result for 2T -dependent distributions also applies to T -round quantum-LOCAL algorithms. Without loss of generality, we assume that the output labels in all of these model are given on half-edges, that is, pairs of the form (v, e) where v is a node and e is an edge incident to v.

2.2

Locally checkable labeling problems

In this paper, we consider the family of locally checkable labeling (LCL) problems, introduced in [34]. We here focus on a simpler—yet equivalent—definition of LCL problems, which is specific to trees: the family of node-edge checkable problems [9]. In this definition, an LCL problem is specified by a finite set of node constraints CN and a finite set of half-edge constraints CE , where a node configuration is a multiset of input and output labels that can appear on the half-edges incident to a node, and a half-edge configuration is a pair of input and output labels that can appear on the two half-edges corresponding to an edge. Since CN is finite, it follows that the maximum degree of the input graph, which we denote by ∆, is a constant that is independent of the number of nodes n.

3

Overview of the analysis

Our main technical contribution is a procedure that, given a bounded-dependent distribution with locality T = no(1) for a node-edge checkable problem Π, produces a randomized LOCAL algorithm with locality O(poly(T log n)) that solves Π. By known gap results [20], since O(poly(T log n)) = no(1) , it holds that there exists a deterministic LOCAL algorithm with locality O(log n) that solves Π. Our randomized algorithm has two stages: We first perform a rake-and-compress type decomposition of the input tree, which allows us to divide the input graph into small components that follow a hierarchical structure. Then, we sample the output labels from the boundeddependent distribution for each component of the decomposition, starting from the highest layer in the hierarchy and proceeding downwards. The sampling procedure is not trivial, as we need to ensure that the output labels sampled for each component are consistent with those sampled for the upper layers of the hierarchy (since the algorithm does not have global view), and that the overall sampling procedure works with high probability. The issue here is that the boundeddependent distribution has dependencies at distances at most 2T , and when two components

3

meet in downward layers, we need to make sure that the two distributions are compatible with each other.

3.1

Hierarchical decomposition of a tree

The hierarchical decomposition that we use is obtained through a rake-and-compress style decomposition. Rake-and-compress has been extensively used in the literature [5, 17, 18, 20, 33]. It works roughly as follows: Given a forest G = (V, E), the nodes of the forest are decomposed into a sequence of pairwise disjoint sets V = V1R ∪ V1C ∪ V2R ∪ V2C ∪ V3R ∪ V3C ∪ . . . where the subscript and superscript together indicate the level of the decomposition, and the superscript indicates the type of the level, which is either rake (denoted by R) or compress R C (denoted by C). We denote the forest induced by nodes ViR ∪ ViC ∪ Vi+1 ∪ Vi+1 ∪ · · · by GRi , and C R C C the forest induced by nodes Vi ∪ Vi+1 ∪ Vi+1 ∪ · · · by Gi . Let L be the smallest integer i such that GCi is the empty graph. Given two parameters ℓ ≥ 1 and γ ≥ 1, the decomposition satisfies the following two key properties: 1. Each connected component of the subgraph induced by ViR must be a rooted tree of height at most γ − 1 such that the root has at most one neighbor in GCi , while other nodes have no neighbors in GCi . 2. Each connected component of the subgraph induced by ViC must be a path on a number of nodes in the range [ℓ, 2ℓ] such that the endpoints have at most one neighbor in GRi+1 , while intermediate nodes have no neighbors in GRi+1 . If the path has one node, then this single node can have at most two neighbors in GRi+1 . A decomposition satisfying these properties is called a (γ, ℓ)-decomposition. We order the layers as V1R , V1C , V2R , V2C , . . .. For later use, for each connected component C of a layer, we define the upward-component of C, denoted C + , as the union of all components reachable from C by a path that visits components in strictly increasing layer order. Equivalently, starting from C, we repeatedly add neighboring components that belong to higher layers. While many algorithms for this decomposition have been already given in previous works, we need an algorithm that takes care of the case in which both γ and ℓ are non-constant parameters. In the appendix, we prove the following theorem. Theorem 3.1. Let γ, ℓ ≥ 1 be integers. There exists a deterministic LOCAL algorithm A that computes a (γ, ℓ)-decomposition of a forest of n nodes with L = O(⌈ℓ/γ⌉ log n) levels in time O((γ + ℓ2 + ℓ log∗ n)⌈ℓ/γ⌉ log n). A key property of any (γ, ℓ)-decomposition is the following lemma, whose proof we leave in the appendix. Lemma 3.2. Let γ, ℓ ≥ 1 be integers, let G be a forest, and let V = V1R ∪ V1C ∪ V2R ∪ V2C ∪ V3R ∪ V3C ∪ . . . be a (γ, ℓ)-decomposition of G. Let C be a connected component in one of the layers VjR or VjC . Then for every layer Vi (either ViR or ViC ), it holds that any two components C1 and C2 of Vi ∩ C + are at distance at least ℓ + 1 from each other. 4

4

Sampling procedure

In this section, we present a LOCAL algorithm that uses a bounded-dependence distribution to produce a solution for an LCL problem Π. Formally, we prove the following lemma which, combined with theorem 3.1, gives the full algorithm: Lemma 4.1. Let Π be an LCL problem on forests, and let Out be a bounded-dependence distribution with locality T (n) that works with high probability. Then, there exists a LOCAL algorithm that, given a (T (n), 2T (n))-decomposition of the input graph G with size n, solves problem Π with high probability and locality O(T (n) log n).

4.1

Sampling algorithm

Let n be the size of the input instance, and let c > 0 be the constant of “with high probability”. We fix the probability constant1 of the bounded-dependence distribution Out to c + 3, we fix its locality T = T (n). Let V = V1R ∪ V1C ∪ V2R ∪ V2C ∪ · · · ∪ VLR be a (T, 2T )-decomposition, which can be computed using theorem 3.1. The randomized LOCAL algorithm works by labeling the nodes according to this decomposition, starting from VLR and proceeding downwards. Each layer of the decomposition consists of multiple components which the algorithm handles in parallel: for each component C of the layer currently being processed, the algorithm samples Out conditioned on what has been sampled in its neighboring higher components C + \ C.

4.2

Analysis

Proof of Lemma 4.1. We first start by analyzing the locality of the above LOCAL algorithm, and then we analyze its correctness. For the locality, note that each connected component induced by the nodes of any given layer have diameter at most O(T ); this is because rake components have radius T by construction, and compress components have length at most 4T by construction. The sampling also needs access to the previously-sampled values of the neighboring higher components C + \ C; we handle this by carrying the values downwards with the sampling: when a component is handled, it can read the sampled values of the higher-level components from its neighboring components, do the local sampling, and propagate the previous sample and the new sample to all nodes of the component – all with locality O(T ). Therefore, the sampling within each component can be done with locality O(T ). As there are L = O(log n) layers, the algorithm takes in total O(T log n) locality. It remains to prove that the algorithm works correctly with probability at least 1 − 1/nc : we prove this using the union bound over local failure probabilities. Intuitively, if the algorithm produces an error somewhere with too large of a probability, then there exists a sampling order that produces genuine sample from the original distribution with the same failure probability. Fix a node v, and consider the probability pv that the LOCAL algorithm fails to label the node correctly, that is, the label of v is not in CN . Let Vi (either ViR or ViC ) be the layer in which node v resides, and let C be the corresponding connected component of Vi . Let C + be the upward-component of C. Consider now the global sampling process where we sample the nodes of C C + from the highest layer downwards: first VLR ∩ C + , then VL−1 ∩ C + conditioned on the output 1 Some authors mean by “with high probability” the case of c = 1. In this case, instead of picking the constant of “with high probability”, we lie to the underlying distribution that the graph has n3 nodes; this gives us the needed boost in success probability while still keeping the locality of the underlying distribution no(1) .

5

R of VLR ∩ C + , then VL−1 ∩ C + conditioned on both higher layers, and so on, until we reach layer Vi . Note that this produces a genuine sample from distribution Out for all nodes of C + . The key observation is that this produced distribution on C + matches exactly the distribution that the LOCAL algorithm produces.2 This is because the LOCAL algorithm carries these sampling dependencies down. A rake component has at most one neighboring component in higher layers. A compress component may have two such neighboring components, but the two upward-components rooted at them are separated by the compress path, which contains at least 2T nodes. Hence the two upward-components are at distance at least 2T + 1, and their samples are independent in the original distribution Out by Lemma 3.2. Thus sampling the two sides separately, and then sampling the compress component conditioned on both sides, gives the same distribution as the global top-down sampling. Therefore, the output distribution of node v must match that of the original distribution Out, and in particular, it cannot fail with probability higher than 1/nc+3 , as otherwise the original distribution would fail with at least this probability. Using similar analysis, we can also bound the probability that the output of an edge violates CE is at most 1/nc+3 . Now, for the LOCAL algorithm to fail, it must fail locally at a node or at an edge. As the graph has n nodes and at most n − 1 edges, the total failure probability can be bounded by the union bound: " #  [   [  1 1 1 Pr node v fails ∪ edge e fails ≤ n · c+3 + (n − 1) · c+3 ≤ c n n n v∈V (G)

e∈E(G)

Therefore, the LOCAL algorithm works with probability at least 1 − 1/nc , completing the proof. We can now proof the main theorem of this paper: Theorem 4.2. Let Out be a bounded-dependence distribution solving an LCL problem Π on forests with locality no(1) and with high probability. Then there exists a deterministic LOCAL algorithm that solves problem Π with locality O(log n). Proof. Let T (n) = no(1) be the locality of the bounded-dependence distribution Out. Combining theorem 3.1 and Lemma 4.1, we get a randomized LOCAL algorithm that solves Π with locality
O (T 2 (n) + T (n) log∗ n) log n = no(1) . We combine this with an existing speed-up result on LCL problems in trees to get an algorithm with locality O(log n) [20].

2 However, this does not necessarily hold for all nodes of the graph.

6

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. [2] Heger Arfaoui and Pierre Fraigniaud. What can be computed without communications? SIGACT News, 45(3):82–104, 2014. [3] Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy, Francesco D’Amore, Massimo Equi, François Le Gall, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, Marc-Olivier Renou, Jukka Suomela, Lucas Tendick, and Isadora Veeren. Distributed quantum advantage for local problems. 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 451–462. ACM, 2025. [4] Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela. Lower bounds for maximal matchings and maximal independent sets. Journal of the ACM, 68(5):39:1–39:30, 2021. [5] Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, and Gustav Schmid. On the node-averaged complexity of locally checkable problems on trees. In Rotem Oshman, editor, 37th International Symposium on Distributed Computing, DISC 2023, October 10-12, 2023, L’Aquila, Italy, volume 281 of LIPIcs, pages 7:1–7:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. [6] Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela. How much does randomness help with locally checkable problems? In Yuval Emek and Christian Cachin, editors, PODC ’20: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020, pages 299–308. ACM, 2020. [7] Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela. Almost global problems in the LOCAL model. Distributed Computing, 34(4):259–281, 2021. [8] Alkida Balliu, Filippo Casagrande, Francesco d’Amore, Massimo Equi, Barbara Keller, Henrik Lievonen, Dennis Olivetti, Gustav Schmid, and Jukka Suomela. Distributed quantum advantage in locally checkable labeling problems. In Kasper Green Larsen and Barna Saha, editors, Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 1268–1308. SIAM, 2026. [9] Alkida Balliu, Keren Censor-Hillel, Yannic Maus, Dennis Olivetti, and Jukka Suomela. Locally checkable labelings with small messages. In Seth Gilbert, editor, 35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference), volume 209 of LIPIcs, pages 8:1–8:18. Schloss Dagstuhl - LeibnizZentrum für Informatik, 2021. [10] Alkida Balliu, Corinna Coupette, Antonio Cruciani, Francesco D’Amore, Massimo Equi, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, and Jukka Suomela. New limits on distributed quantum advantage: Dequantizing linear programs. In Dariusz R. Kowalski,

7

editor, 39th International Symposium on Distributed Computing, DISC 2025, October 2731, 2025, Berlin, Germany, volume 356 of LIPIcs, pages 11:1–11:22. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2025. [11] Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, Augusto Modanese, Dennis Olivetti, Mikaël Rabie, Jukka Suomela, and Jara Uitto. Shared randomness helps with local distributed problems. In Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis, editors, 52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, July 8-11, 2025, Aarhus, Denmark, volume 334 of LIPIcs, pages 16:1–16:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. [12] Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, and Jukka Suomela. New classes of distributed time complexity. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1307–1318. ACM, 2018. [13] Leonid Barenboim, Michael Elkin, and Uri Goldenberg. Locally-iterative distributed (∆ + 1)coloring and applications. Journal of the ACM, 69(1):5:1–5:26, 2022. [14] Sebastian Brandt. An automatic speedup theorem for distributed problems. 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 379–388. ACM, 2019. [15] Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto. A lower bound for the distributed Lovász local lemma. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 479–488. ACM, 2016. [16] Keren Censor-Hillel, Orr Fischer, François Le Gall, Dean Leitersdorf, and Rotem Oshman. Quantum distributed algorithms for detection of cliques. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, volume 215 of LIPIcs, pages 35:1–35:25. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2022. [17] Yi-Jun Chang. The complexity landscape of distributed locally checkable problems on trees. In Hagit Attiya, editor, 34th International Symposium on Distributed Computing, DISC 2020, October 12-16, 2020, Virtual Conference, volume 179 of LIPIcs, pages 18:1–18:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. [18] Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto. The complexity of distributed edge coloring with small palettes. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2633–2652. SIAM, 2018. [19] 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. [20] Yi-Jun Chang and Seth Pettie. A time hierarchy theorem for the LOCAL model. SIAM Journal on Computing, 48(1):33–69, 2019. 8

[21] Xavier Coiteux-Roy, Francesco D’Amore, Rishikesh Gajjala, Fabian Kuhn, François Le Gall, Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou, Gustav Schmid, and Jukka Suomela. No distributed quantum advantage for approximate graph coloring. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 1901–1910. ACM, 2024. [22] Sameep Dahal, Francesco D’Amore, Henrik Lievonen, Timothé Picavet, and Jukka Suomela. Brief announcement: Distributed derandomization revisited. In Rotem Oshman, editor, 37th International Symposium on Distributed Computing, DISC 2023, October 10-12, 2023, L’Aquila, Italy, volume 281 of LIPIcs, pages 40:1–40:5. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. [23] Francesco d’Amore. On the limits of distributed quantum computing. Bulletin of the EATCS, 145:51–91, 2025. [24] Anubhav Dhar, Eli Kujawa, Henrik Lievonen, Augusto Modanese, Mikail Muftuoglu, Jan Studený, and Jukka Suomela. Local problems in trees across a wide range of distributed models. In Silvia Bonomi, Letterio Galletta, Etienne Rivière, and Valerio Schiavoni, editors, 28th International Conference on Principles of Distributed Systems, OPODIS 2024, December 11-13, 2024, Lucca, Italy, volume 324 of LIPIcs, pages 27:1–27:17. Schloss Dagstuhl - LeibnizZentrum für Informatik, 2024. [25] Pierre Fraigniaud, Marc Heinrich, and Adrian Kosowski. Local conflict coloring. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 625–634. IEEE Computer Society, 2016. [26] Cyril Gavoille, Adrian Kosowski, and Marcin Markiewicz. What can be observed locally? In Idit Keidar, editor, Distributed Computing, 23rd International Symposium, DISC 2009, Elche, Spain, September 23-25, 2009. Proceedings, volume 5805 of Lecture Notes in Computer Science, pages 243–257. Springer, 2009. [27] Taisuke Izumi and François Le Gall. Quantum distributed algorithm for the all-pairs shortest path problem in the CONGEST-CLIQUE model. 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 84–93. ACM, 2019. [28] François Le Gall. Quantum distributed computing. In 11th Workshop on Advances in Distributed Graph Algorithms (ADGA 2022), 2022. [29] François Le Gall and Frédéric Magniez. Sublinear-time quantum computation of the diameter in CONGEST networks. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, pages 337–346. ACM, 2018. [30] François Le Gall, Harumichi Nishimura, and Ansis Rosmanis. Quantum advantage for the LOCAL model in distributed computing. In Rolf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany, volume 126 of LIPIcs, pages 49:1–49:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. [31] Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193–201, 1992. 9

[32] Yannic Maus and Tigran Tonoyan. Local conflict coloring revisited: Linial for lists. In Hagit Attiya, editor, 34th International Symposium on Distributed Computing, DISC 2020, October 12-16, 2020, Virtual Conference, volume 179 of LIPIcs, pages 16:1–16:18. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2020. [33] Gary L. Miller and John H. Reif. Parallel tree contraction and its application. In 26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, USA, 21-23 October 1985, pages 478–489. IEEE Computer Society, 1985. [34] Moni Naor and Larry J. Stockmeyer. What can be computed locally? SIAM Journal on Computing, 24(6):1259–1277, 1995. [35] Jukka Suomela. Landscape of locality (invited talk). In Susanne Albers, editor, 17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020, June 22-24, 2020, Tórshavn, Faroe Islands, volume 162 of LIPIcs, pages 2:1–2:1. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2020.

10

A

Preliminaries

In this section, we introduce all the basic definitions and notations that we will use throughout the paper, and we also give a brief overview of the models of computation and probabilistic models that we will be working with. Graphs We work with simple, undirected graphs G = (V, E), where V is the set of nodes and E is the set of edges. When the sets of nodes and edges are not specified, we can refer to them as V (G) and E(G), respectively. Given any two nodes u, v ∈ V , we denote by dist(u, v) the distance between u and v in G, that is, the length of the shortest path between u and v in G. The distance between a node v and a set of nodes S ⊆ V is defined as dist(v, S) = minu∈S dist(v, u). Similarly, the distance between two sets of nodes S, T ⊆ V is defined as dist(S, T ) = minu∈S,v∈T dist(u, v). The diameter of G is defined as diam(G) = maxu,v∈V dist(u, v). The eccentricity of a node v is defined as the maximum length of a shortest path from v to any other node in G, that is, ecc(v) = maxu∈V dist(u, v). For any node v ∈ V , we denote by N (v) = {u ∈ V : dist(u, v) = 1} the open neighborhood of v in G. All the elements of N (v) are called the neighbors of v. We also define the closed neighborhood of v as N [v] = N (v) ∪ {v}. For any integer r ≥ 0, we denote by N r [v] = {u ∈ V : dist(u, v) ≤ r} the set of nodes that are at distance at most r from v in G, and by N r (v) = {u ∈ V : dist(u, v) = r} the set of nodes that are at distance exactly r from v in G. We extend the definition of neighborhood to sets of nodes as well, by defining N (S) = {u ∈ V : dist(u, S) = 1}, N [S] = {u ∈ V : dist(u, S) ≤ 1}, N r (S) = {u ∈ V : dist(u, S) = r}, and N r [v] = {u ∈ V : dist(u, S) ≤ r} for any S ⊆ V . Given a set of nodes S ⊆ V , we denote by G[S] the subgraph of G induced by the nodes of S. Given two graphs G = (VG , EG ) and H = (VH , EH ), we say that G and H are isomorphic if there exists a bijection φ : VG → VH such that {u, v} ∈ EG if and only if {φ(u), φ(v)} ∈ EH . The union of two graphs G = (VG , EG ) and H = (VH , EH ) is defined as the graph G ∪ H = (VG ∪ VH , EG ∪ EH ). The difference of two graphs G = (VG , EG ) and H = (VH , EH ) is defined as the graph G \ H = (VG , EG \ EH ). Half-edges Consider any graph G = (V, E). We define the set of half-edges of G as the set H(G) = {(v, e) : v ∈ V, e ∈ E, v ∈ e}. Any element of H(G) is called a half-edge of G, and it can be thought of as the part of the edge that is incident to only one of its endpoints. Hence, any edge e = {u, v} ∈ E corresponds to two half-edges, namely (u, e) and (v, e). Edge-labeled graph Let Σ be a set of labels. A Σ-edge-labeled graph is a tuple (G = (V, E), λ) where G is a graph, and λ : H(G) → Σ is a function that assigns a label from Σ to each half-edge in H(G). The function λ is called the labeling of G. Centered graphs Let r ≥ 0 be an integer. A centered graph of radius r is a tuple (G, v) where G is a graph and v ∈ V (G) is a node such that the eccentricity of v in G is at exactly r, that is, ecc(v) = r, with the following properties: First, we have N r [v] = V (G). Second, if u1 , u2 ∈ V (G) are such that dist(v, u1 ) = dist(v, u2 ) = r, then u1 and u2 are not adjacent in G. Note that this matches exactly what an r-round LOCAL algorithm can gather about the graph at every node.

11

Set of constraints Let Σ be a set of labels, and let r, ∆ ≥ 0 be integers. An (r, ∆)-set of constraints over Σ is a family C = {(Gi , λi , vi )}i∈I where, for each (Gi , λi , vi ) ∈ C, we have that (Gi , vi ) is a centered graph of radius at most r and maximum degree at most ∆, λi : H(Gi ) → Σ is a labeling function, and (Gi , λi ) is a Σ-edge-labeled graph. A Σ-edge-labeled graph (G, λ) is said to satisfy C if for any node v ∈ V (G), there exists some (Gi , λi , vi ) ∈ C such that the G[N r [v]] \ G[N r (v)] in G is isomorphic to Gi , and the isomorphism maps v to vi and preserves the half-edge labels. Locally checkable labeling problem Let Σin , Σout be two finite sets of labels, and r, ∆ ≥ 0 be integers. A locally checkable labeling (LCL) problem Π is a tuple (Σin , Σout , r, ∆, C), where C is a finite (r, ∆)-set of constraints over Σin × Σout . Solving Π means the following: given as input a Σin -edge-labeled graph (G, λin ), where λin : H(G) → Σin is the input labeling of the graph, the goal is to produce an output labeling λout : H(G) → Σout such that, having defined λ : H(G) → Σin ×Σout with λ(v, e) = (λin (v, e), λout (v, e)), we have that (G, λ) satisfies C. Node-edge checkable problems We define an alternative notion of locally checkable labeling problems which at first seems more restrictive than the one defined above, but is in fact equivalent to it [9]. Let Σin , Σout be two finite sets of labels, and ∆ ≥ 0 be an integer. We specify the LCL problem through two sets of constraints CV and CE . The first set CV is a set of elements, which we call node constraints, where each element is a multiset of at most of at most ∆ elements, and each element belongs to Σin × Σout . The second set CE is a set of elements, which we call edge constraint, where each element is a multiset of two elements, and each element of the multiset belongs to Σin × Σout . Hence, the LCL problem can be defined via the tuple (Σin , Σout , ∆, CV , CE ). Solving Π means the following: given as input a Σin -edge-labeled graph (G, λin ), where λin : H(G) → Σin is the input labeling of the graph, the goal is to produce an output labeling λout : H(G) → Σout such that the following holds: • For each node v ∈ V (G), the multiset of labels {λ(v, e) : e ∈ E(G), v ∈ e} belongs to CV . • For each edge e = {u, v} ∈ E(G), the multiset of labels {λ(u, e), λ(v, e)} belongs to CE . It has been proven that the two definitions of the LCL problems are equivalent in trees for the LOCAL model, in the sense that, for any LCL problem defined according to the first definition, there exists an equivalent LCL problem defined according to the second definition, and vice versa, and there are constant-time LOCAL algorithms that can transform any solution of the first problem into a solution of the second problem, and vice versa [9]. For simplicity, in the rest of the paper we will just work with node-edge checkable problems.

A.1

Models of computation

The LOCAL model We work in the classical LOCAL model of distributed computation [31]. In this model, we are given n computing units (called nodes) that are connected by a communication network. The communication network is modeled as an undirected graph G = (V, E) where the nodes of the 12

graph correspond to the computing units, and the edges correspond to communication links between the nodes. The nodes run the same algorithm and operate in synchronous rounds, and in each round, the nodes perform the following steps: First, they perform some local computation based on their current state and the information they have received from their neighbors in the previous rounds. Then, they send messages to and receive messages from their neighbors. Note that in the LOCAL model there is no limit on the size of the messages that can be sent in each round, and there is no limit on the amount of local computation that can be performed by the nodes in each round. At the beginning of computation, all nodes are identical, except for a unique identifier of O(log n) bits, which is used to break symmetry in the computation, their degree, and the port numbers of their incident edges. The nodes may also have access to some additional (distinguished) input which is part of the problem specification. The computation ends when all nodes have decided on their output, and the running time of the algorithm is the number of communication rounds until all nodes have decided on their output. The complexity of a problem in the LOCAL model is measured by the minimum number of rounds of any algorithm that solves the problem in the LOCAL model. Nodes may be given access to independent sources of infinite random bits strings, in which case we talk about the randomized LOCAL model as opposed to the deterministic LOCAL model. In the randomized LOCAL model, we require that a problem is solved with high probability, that is, for any given c > 0, the algorithm must solve the problem with probability at least 1 − 1/nc . Input graph As already mentioned, the input graph is the network communication graph. Nodes have unique identifiers of size O(log n) bits, where n is the number of nodes in the network, and can distinguish the communication links towards their neighbors through port numbers from 1 up to the degree of the node. Both identifiers and port numbers are adversarially chosen and part of the input graph, unrelated to the specific problem we are solving. The input labels of the problem of interest, the identifiers and port numbers, and the inital states of the nodes, possibly together with the random bits, are encoded in some local variable inpt(v), where v ∈ V (G). Local view Let r ≥ 0 be any integer. Given a graph (G, inpt) as input to some problem in the LOCAL model, for any v ∈ V (G), we define the radius-r view of v, denoted by V r (v, G, inpt), as the graph Gr (v) = G[N r [v]] \ G[N r (v)], where each node u ∈ V (Gr (v)) is equipped with its own local variable inpt(u). The radius-r view of a subset of nodes A ⊆ V (G) is analogously defined, and is denoted by V r (A, G, inpt). Given two input graphs (G, inptG ) and (H, inptH ), and two subsets of nodes A ⊆ V (G) and B ⊆ B(H), we say that V r (A, G, inptG ) is isomorphic to V r (B, H, inptH ) if there exists an isomorphism φ between Gr (A) and Hr (B) such that the following holds: 1. φ ↾A is an isomorphism between G[A] and H[B]. 2. inptH (φ(v)) = inptG (v) for each v ∈ V (Gr (A)). The quantum-LOCAL model The quantum-LOCAL model is a quantum extension of the LOCAL model, where the nodes are quantum computing units that exchange quantum messages. More specifically, the nodes can manipulate an arbitrary number of qubits by applying unitaries, perform any kind of measurements on their local states, and exchange messages of arbitrary size with their neighbors. The output of the algorithm is determined by the measurement outcomes of the nodes at the end of the 13

computation, and the complexity of a problem in the quantum-LOCAL model is measured by the minimum number of rounds of any quantum algorithm that solves the problem in the quantum-LOCAL model. Similarly to the randomized LOCAL model, we require that a problem is solved with high probability in the quantum-LOCAL model as well. For a formal definition of the model, see [26].

A.2

Probabilistic models

Note that randomized and quantum-LOCAL algorithms produce probability distributions over output labelings of the input graph. We formalize this concept following the definitions of Akbari et al. [1]. Outcomes Let Σ be a set of labels. An outcome is a function Out : (G, inpt) 7→ {(λi , pi )}i∈I mapping each input graph (G, inpt) to a probability distribution over labeling functions, that is, a family {(λi , pi )}i∈I where I ⊆ R is any Lebesgue-measurable set of indices, λi : H(G) → Σ is a labeling function, and pi is the probability that G is actually labeled by λi . Note that it must hold that P = 1, and that each pi is non-negative. If I is uncountable, p i i∈I R p : I → [0, 1] is a measurable density function and the sum is meant to be an integral, that is, I p(x) dx = 1. We remark that an outcome must be defined for every input graph, just like a LOCAL algorithm can be executed on every input graph. Indeed, if at any node of a graph and at any round, the computation specified by an algorithm is undefined, we can assume that the node can always output some garbage label ⊥. Given a subgraph G′ ⊆ G, the restriction Out(G, inpt) ↾(G′ ,inpt↾V (G′ ) ) of the probability distribution Out(G, inpt) = {(λi , pi )}i∈I to (G′ , inpt ↾V (G′ ) ) is the probability distribution {(ηj , qj )}j∈J where J ⊆ I, ηj : H(G′ ) → Σ is such that there exists i ∈ I with λi ↾H(G′ ) = ηj , and qj =

X

pi .

i∈I : λi ↾H(G′ ) =ηj

The sum is replaced by an integral when suitable. Non-signaling outcomes Let Out be any outcome. We say that Out is non-signaling beyond distance T = T (n) if, for any two input graphs (G, inptG ) and (H, inptH ) of n nodes such that there exists two subsets of nodes A ⊆ V (G) and B ⊆ V (H) with V T (A, G, inptG ) that is isomorphic to V T (A, H, inptH ), then the probability distributions Out(G, inptG ) ↾(G[A],inptG ↾A ) and Out(H, inptH ) ↾(H[B],inptH ↾B ) are the same. T-dependent distributions Given an input graph (G, inptG ) and a probability distribution {(λi , pi )}i∈I over labelings of G, we say that {(λi , pi )}i∈I is T -dependent if, for any two subsets of nodes A, B ⊆ V (G) such that dist(A, B) > T , the probability distributions obtained by the restrictions of {(λi , pi )}i∈I to (G[A], inpt ↾A ) and to (G[B], inpt ↾B ) are independent.

14

The bounded-dependence model In the bounded-dependence model, the input graph is as in the classical LOCAL model, and we produce outcomes. We say that an outcome Out in the bounded-dependence model has locality T = T (n) if the following properties are satisfied: 1. Out is non signaling beyond distance T . 2. Given an input graph (G, inpt), the probability distribution Out(G, inpt) is 2T -dependent. If T (n) = O(1) independently of n, we say that the probability distributions generated by Out are finitely-dependent. Similarly to the classical LOCAL model, an outcome is required to solve the problem with high probability.

B

Hierarchical decomposition of a tree

In this section, we show how to perform a hierarchical decomposition of a tree into smaller pieces. At the end of this decomposition, the nodes of the tree are decomposed into a sequence of pairwise disjoint sets V1R , V1C , V2R , V2C , . . ., where the subscript and superscript together indicate the level of the decomposition, and the superscript indicates the type of the level, which is either rake (denoted by R) or compress (denoted by C). We denote the forest induced by nodes R C R C ViR ∪ ViC ∪ Vi+1 ∪ Vi+1 ∪ · · · by GRi , and the forest induced by nodes ViC ∪ Vi+1 ∪ Vi+1 ∪ · · · by C C Gi . Let L be the smallest integer i such that Gi is the empty graph. Given two parameters ℓ ≥ 1 and γ ≥ 1, the decomposition satisfies the following two key properties: 1. Each connected component of the subgraph induced by ViR must be a rooted tree of height at most γ − 1 such that the root has at most one neighbor in GCi , while other nodes have no neighbors in GCi . 2. Each connected component of the subgraph induced by ViC must be a path on a number of nodes in the range [ℓ, 2ℓ] such that the endpoints have at most one neighbor in GRi+1 , while intermediate nodes have no neighbors in GRi+1 . If the path has one node, then this single node can have at most two neighbors in GRi+1 . A decomposition satisfying these properties is called a (γ, ℓ)-decomposition. We order the layers as V1R , V1C , V2R , V2C , . . .. For later use, for each connected component C of a layer, we define the upward-component of C, denoted C + , as the union of all components reachable from C by a path that visits components in strictly increasing layer order. Equivalently, starting from C, we repeatedly add neighboring components that belong to higher layers.

B.1

A rake-and-compress algorithm for the decomposition

We now describe the decomposition procedure. Algorithm 1 is described in a centralized manner. The purpose of this centralized description is to specify the shape of the levels. Afterward, we explain why the same phase structure can be implemented in the deterministic LOCAL model. The algorithm proceeds in phases. At the beginning of a phase i, F is the forest induced by the nodes that have not yet received a rake or compress level. The parameter γ is the length scale used in the rake step, while ℓ is the length scale used in the compress step. The phase starts with a rake step. The rake step consists of γ rake operations. In each operation, all current isolated nodes and leaves of the remaining forest are removed, except that if

15

Algorithm 1 Tree-decomposition Require: A forest G = (V, E), integers γ, ℓ ≥ 1 Ensure: A (γ, ℓ)-decomposition (V1R , V1C , . . . , VLR , VLC ) of G, with L = O(⌈ℓ/γ⌉ log n) 1: F ← G 2: i ← 1 3: while V (F ) ̸= ∅ do ▷ Rake step 4: ViR ← ∅ 5: Frake ← F 6: for t = 1, 2, . . . , γ do 7: Rt ← RakeStep(Frake ) 8: ViR ← ViR ∪ Rt 9: Frake ← Frake [V (Frake ) \ Rt ] 10: end for 11: F ← Frake 12: if V (F ) = ∅ then 13: ViC ← ∅ 14: break 15: end if ▷ Compress step 16: ViC ← CompressPaths(F, ℓ) 17: F ← F [V (F ) \ ViC ] 18: i←i+1 19: end while 20: L ← i 21: return (V1R , V1C , . . . , VLR , VLC )

a connected component is a single edge, then only the endpoint with larger identifier is removed. The union of the nodes removed by these γ operations is the next rake level ViR . After the rake step, if any nodes remain, the phase performs a compress step. The compress step scans each maximal degree-2 path, meaning a maximal path whose nodes all have degree 2 in the current forest, and removes long intervals between kept boundary nodes. Each removed interval contains between ℓ and 2ℓ nodes. The boundary nodes remain in the forest, so only the endpoints of the removed pieces can have neighbors in the next forest.

B.2

Correctness of the decomposition algorithm

Lemma B.1. If Algorithm 1 terminates, it returns a partition of V (G). Proof. Each nonempty set ViR or ViC is a subset of the current forest F , and after assigning it, the algorithm replaces F by the induced forest on the remaining nodes. Hence, no node can be assigned to two different levels. The algorithm terminates only after F is empty, because the last rake removal emptied the forest. Therefore, every node is assigned to exactly one level. With the next lemma, we prove that the rake components satisfy the required properties. Lemma B.2. Let C be a connected component of G[ViR ]. Then C can be rooted with height at most γ − 1 so that the root has at most one neighbor in GCi , while all other nodes of C have no neighbors in GCi . 16

Algorithm 2 RakeStep(F ) Require: A forest F Ensure: A set R ⊆ V (F ) of nodes to be removed by one rake operation 1: R ← {v ∈ V (F ) : degF (v) = 0} 2: R ← R ∪ {v ∈ V (F ) : v has unique neighbor u, and either degF (u) ≥ 2 or id(v) > id(u)} 3: return R Algorithm 3 CompressPaths(F, ℓ) Require: A forest F , an integer ℓ ≥ 1 Ensure: A set X ⊆ V (F ) of nodes to be removed as compress components 1: X ← ∅ 2: for all maximal paths P = v1 . . . vk whose nodes all have degree 2 in F do 3: if k − 2 ≥ ℓ then 4: s←1 5: while k − s − 1 ≥ ℓ do 6: if k − s − 1 ≤ 2ℓ then 7: q←k 8: else 9: q ← s + 2ℓ + 1 10: end if 11: X ← X ∪ {vj : s < j < q} 12: s←q 13: end while 14: end if 15: end for 16: return X Proof. Let Fi be the forest at the beginning of phase i. The nodes of GCi are precisely the nodes of Fi − ViR . For every node v ∈ C, let t(v) ∈ {1, . . . , γ} be the rake operation in which v is removed. At the moment v is removed, it has degree at most 1 in the current forest. Hence v has at most one neighbor whose removal time is larger than t(v), or which remains after the rake step. Moreover, two adjacent nodes cannot be removed in the same rake operation: the only case in which two adjacent nodes are both leaves is a single-edge component, and then the identifier tie-break removes only one endpoint. In a connected component C of G[ViR ], root C at the unique node with no neighbor in C of larger removal time. Uniqueness follows because G[C] is a tree: if two such nodes existed, the path between them inside C would contain a node with two neighbors that survive longer, contradicting that this node was a leaf when removed. Along every path towards the root, removal times strictly increase, and therefore the height of C is at most γ − 1. The root is the only node of C that can have a neighbor in Fi − ViR , and it has at most one such neighbor, while all other nodes of C have no neighbors in Fi − ViR . The next lemma proves that the compress components satisfy the required properties. Lemma B.3. Let C be a connected component of G[ViC ]. Then C is a path on a number of nodes in the range [ℓ, 2ℓ]. If C has at least two nodes, then the endpoints have at most one neighbor in GRi+1 , while intermediate nodes have no neighbors in GRi+1 . If C consists of a single node, then 17

this node has at most two neighbors in GRi+1 . Proof. If ViC = ∅, there is nothing to prove. Otherwise, let Fi be the forest just before ViC is removed. A component C produced by the compress step is the interval vs+1 . . . vq−1 inside some maximal degree-2 path P = v1 . . . vk of Fi . All nodes of P have degree 2 in Fi . The nodes vs and vq are not added to ViC , and hence they remain in Fi − ViC . They are adjacent to C, and they are the only possible neighbors of C in Fi − ViC . The nodes of Fi − ViC are exactly the nodes that have not yet been assigned after the compress step, and these induce GRi+1 . If C has at least two nodes, then its endpoints are adjacent to at most one of vs and vq , while its intermediate nodes are adjacent to neither. If C consists of the single node vs+1 = vq−1 , then this node is adjacent to both vs and vq , and has no other neighbor in GRi+1 . Hence it has at most two neighbors in GRi+1 . The compress step chooses q so that ℓ ≤ q − s − 1 ≤ 2ℓ. Thus the removed interval C contains q − s − 1 nodes, which is in the range [ℓ, 2ℓ]. Wrapping up, we conclude with the following lemma. Lemma B.4. The output of Algorithm 1 is a (γ, ℓ)-decomposition of G. Proof. By Lemma B.1, the output is a partition. Lemma B.2 proves property 1 with parameter γ, and Lemma B.3 proves property 2 with parameter ℓ. Thus, every condition in the definition of a (γ, ℓ)-decomposition is satisfied. Progress The next lemma shows that compress steps do not leave very long degree-2 paths, which is a key property for the progress of the algorithm. Lemma B.5. Let F ′ be the forest obtained after applying the compress step to a forest F . Then every maximal degree-2 path of F ′ contains fewer than ℓ + 2 nodes. Proof. Let P = v1 . . . vk be a maximal degree-2 path of F . If k − 2 < ℓ, then P contains fewer than ℓ + 2 nodes, and the compress step does not modify P . If k − 2 ≥ ℓ, the compress step removes the internal nodes of intervals vs . . . vq with q − s − 1 ≥ ℓ. The nodes vs and vq are kept, but after the internal nodes are removed they are no longer connected through that interval. Thus, every remaining connected subpath of P contains fewer than ℓ + 2 nodes that still have degree 2. Since the first and last nodes of every compressed degree-2 path are kept, a node outside P does not lose its incident edge to P during this compression. Hence, separate degree-2 paths cannot merge through such a node. For a forest F , let S(F ) be the forest obtained by contracting every maximal degree-2 path of F into one edge. We call S(F ) the skeleton of F . By construction, S(F ) has no degree-2 nodes. With the next lemma, we show that sequences of rake steps remove all skeleton nodes of degree at most 1, which is a key property for the progress of the algorithm. Lemma B.6. Suppose that every maximal degree-2 path of a forest F contains fewer than ℓ + 2 nodes. Let h = ⌈(ℓ + 3)/γ⌉. After h consecutive rake steps, every node of S(F ) of degree at most 1 has disappeared from the current skeleton. Proof. Let x be a node of S(F ) of degree at most 1. If x is isolated in S(F ), then it is isolated in F and is removed by the first rake operation. Otherwise, in F , the skeleton edge incident to x corresponds to a path xu1 . . . ur y,

18

where r ≥ 0, each node uj has degree 2, and r < ℓ + 2. If the component is just this path, choose either endpoint as x. A rake step consists of γ leaf-removal operations. As long as some node of xu1 . . . ur remains, the first remaining node on the path xu1 . . . ur is a leaf of the current forest. Hence, one rake step removes the next γ nodes of this list, unless the whole list has already been removed. The only exception is when the remaining component is a single edge and the first node of the list has the smaller identifier; in that case the other endpoint is removed first, and the first node is removed in the next leaf-removal operation. After h = ⌈(ℓ + 3)/γ⌉ rake steps, all nodes xu1 . . . ur have been removed, because r + 2 ≤ ℓ + 3 ≤ hγ. Thus, the old skeleton node x, and the path connecting it to the rest of the skeleton, no longer appear in the current skeleton. If we remove all nodes of degree at most 1 from the skeleton of a forest, the number of remaining nodes decreases by a constant factor, as shown by the next lemma. Lemma B.7. Let S be a forest with no degree-2 nodes. If all nodes of degree at most 1 in S are deleted, the number of remaining nodes is at most half of |V (S)|. Proof. Let L be the set of nodes of degree at most 1 in S, and let B be the set of nodes of degree at least 3. Since S has no degree-2 nodes, V (S) = L ∪ B. In every forest, |B| ≤ |L|. Hence, after deleting L, at most |B| ≤ |V (S)|/2 nodes remain. The following result concludes the analysis of the progress of the algorithm. Lemma B.8. Algorithm 1 creates O(⌈ℓ/γ⌉ log n) levels. Proof. Let h = ⌈(ℓ + 3)/γ⌉. After every compress step, the current forest has no maximal degree-2 path with at least ℓ + 2 nodes by Lemma B.5. If the algorithm does not terminate during the first phase, its first compress step establishes this property. Starting from such a forest, Lemma B.6 says that h rake steps would delete all nodes of degree at most 1 in the skeleton present at the beginning of the block. The compress steps performed inside the block only pass to subforests of the forest that would be obtained without compression: they delete nodes and incident edges, and never add nodes or edges. Thus degrees can only decrease, and any node that would become a leaf after some number of leaf-removal operations without these compress steps becomes a leaf no later if the compress steps are also performed, unless it has already been deleted by a compress step. Thus, after the first phase, every block of h phases removes at least all nodes of degree at most 1 in the skeleton present at the beginning of the block. By Lemma B.7, deleting these nodes leaves at most half of the skeleton nodes. Hence, if sj is the skeleton size at the beginning of the j-th such block, then sj+1 ≤ sj /2. Since the initial skeleton has at most n nodes, there are at most 1 + h⌈log2 n⌉ phases. Each phase creates at most one rake level and one compress level, so the number of levels is at most 2 + 2h⌈log2 n⌉ = O(⌈ℓ/γ⌉ log n). We now show that algorithm 1 can be implemented in the deterministic LOCAL model with the same phase structure, and with a cost of O(γ + ℓ2 + ℓ log∗ n) rounds per phase. We first introduce the notion of ruling sets, which are a generalization of maximal independent sets. Definition B.9. Let a, b ≥ 1 be integers. A set S ⊆ V (G) is an (a, b)-ruling set of G if every two distinct nodes of S are at distance at least a, and every node of G is at distance at most b from some node of S. Computing specific ruling sets can be done by computing an MIS in the power graph of the input graph. Deterministic algorithms for MIS have been extensively studied in the literature [13,25,32]. We do not wish to optimize the running time of the ruling set, and the following lemma is enough for our purposes, as we will argue in the following sections. 19

Lemma B.10. Let Pn be an n-node path, and let α ≥ 2. There is a deterministic LOCAL algorithm that computes an (α, α − 1)-ruling set of Pn in O(α2 + α log∗ n) rounds. Proof. Let r = α − 1, and let H = Pnr be the graph on node set V (Pn ) in which two distinct nodes are adjacent if their distance in Pn is at most r. The maximum degree of H is at most 2r = O(α). We compute a deterministic MIS of H using a degree-dependent O(∆ + log∗ n)-round deterministic MIS algorithm [13]. A communication round in H can be simulated in O(α) rounds on the original path Pn , because the neighbors of a node in H are within distance at most r = α − 1 in Pn . Thus, the total cost on Pn is O(α · (∆(H) + log∗ n)) = O(α2 + α log∗ n), where ∆(H) is the maximum degree of H. Let S be the MIS of H. Since S is independent in H, no two nodes of S are at distance at most r in Pn . Hence, distinct nodes of S are at distance at least r + 1 = α in Pn . Since S is maximal in H, every node of Pn is either in S or has a neighbor in S in H, and is therefore within distance r = α − 1 from S in Pn . Thus, S is an (α, α − 1)-ruling set of Pn . The following lemma establishes that one phase of our algorithm 1 can be implemented in the deterministic LOCAL model with a cost of O(γ + ℓ2 + ℓ log∗ n) rounds. Lemma B.11. One phase of the rake-and-compress decomposition can be implemented in O(γ + ℓ2 + ℓ log∗ n) rounds in the deterministic LOCAL model. Proof. The rake level is obtained by simulating γ rounds of leaf removal in the current forest, using identifiers to break symmetry on isolated edges. This takes O(γ) rounds in total. For the compress level, consider the subgraph induced by the degree-2 nodes of the current forest. Its connected components are precisely the maximal degree-2 paths. The LOCAL implementation of the compress step uses separators on these paths rather than the centralized scan of Algorithm 3. Let P = v1 . . . vk be one such path. If k − 2 < ℓ, no node of P is removed. Otherwise, v1 and vk are kept as separators. The nodes within distance at most ℓ from either endpoint are not allowed to become additional separators. On the remaining middle subpath, if it is nonempty, we compute a deterministic (ℓ + 1, ℓ)-ruling set using Lemma B.10, with α = ℓ + 1; this takes O(ℓ2 + ℓ log∗ n) rounds. Let SP be the union of the two endpoints and the ruling-set nodes, ordered along P . Consecutive nodes of SP are at distance at least ℓ + 1: this follows from definition of ruling set, and from the fact that nodes within distance less than ℓ + 1 from an endpoint were not allowed to become separators. Consecutive nodes of SP are also at distance at most 2ℓ + 1: between two ruling-set nodes this follows from the covering condition, and near an endpoint the first eligible node is at distance ℓ + 1 from the endpoint and is within distance at most ℓ from a ruling-set node. If the middle subpath is empty, then k − 2 ≤ 2ℓ, so the two endpoints are at distance at most 2ℓ + 1. The distributed compress step removes exactly the internal nodes between each pair of consecutive separators in SP . Thus, it may choose different separators from the centralized scan in Algorithm 3, but every removed component is still a path on between ℓ and 2ℓ nodes, and its only possible neighbors in the next forest are the two separators. These are precisely the properties used in the correctness and progress proofs. Hence, one complete phase takes O(γ + ℓ2 + ℓ log∗ n) rounds. Now we are ready to conclude with the main result of this section, which states that a (γ, ℓ)-decomposition can be computed in the deterministic LOCAL model with locality O((γ + ℓ2 + ℓ log∗ n)⌈ℓ/γ⌉ log n).

20

Theorem B.12. Let γ, ℓ ≥ 1 be integers. There exists a deterministic LOCAL algorithm A that computes a (γ, ℓ)-decomposition of a forest of n nodes with L = O(⌈ℓ/γ⌉ log n) levels in time O((γ + ℓ2 + ℓ log∗ n)⌈ℓ/γ⌉ log n). Proof. Run the phase-by-phase LOCAL implementation from Lemma B.11. By Lemma B.8, only O(⌈ℓ/γ⌉ log n) phases are needed, and each phase creates at most one rake level and one compress level. By the correctness lemma, the produced levels form a (γ, ℓ)-decomposition. Since each phase costs O(γ + ℓ2 + ℓ log∗ n) rounds, the total running time is O((γ + ℓ2 + ℓ log∗ n)⌈ℓ/γ⌉ log n). A key property of any (γ, ℓ)-decomposition is the following lemma, restated here for reader’s convenience: Lemma 3.2. Let γ, ℓ ≥ 1 be integers, let G be a forest, and let V = V1R ∪ V1C ∪ V2R ∪ V2C ∪ V3R ∪ V3C ∪ . . . be a (γ, ℓ)-decomposition of G. Let C be a connected component in one of the layers VjR or VjC . Then for every layer Vi (either ViR or ViC ), it holds that any two components C1 and C2 of Vi ∩ C + are at distance at least ℓ + 1 from each other. Proof. The lemma holds by induction: Let Vi be the layer containing C. Then clearly Vi ∩ C + contains only on component, C. If Vi is a rake layer, then it has at most one neighboring component C ′ at a higher layer, in which case we can use induction on C ′ . On the other hand, if Vi is a compress layer, then it has at most two neighboring components C ′ and C ′′ in the higher layer. However, as Vi is a path with at least ℓ nodes, then components C ′ and C ′′ have distance at least ℓ + 1. Hence, for components of C ′ and C ′′ , we can inductively apply the lemma for them separately. Finally, there cannot be a subcomponent in C ′ and in C ′′ at any level such that they would be closer than ℓ + 1 from each other as path Vi separates them.

21

Related documents

• Superlogarithmic Gap Result for LCLs on Trees in Quantum-LOCAL#625402
• Superlogarithmic Gap Result for LCLs on Trees in Quantum-LOCAL#623129
• Next-to-Next-to-Leading Order QCD Corrections to $η_t \to HZ$#1119437
• First measurements of absolute branching fractions of the Xi(+)(c) baryon at Belle#630534
• Morse Topology, Zero Products, and Elliptic Prime Crossings#1064506