Source-linked AI summary
On the Complexity of Local Distributed Graph Problems
Mohsen Ghaffari, Fabian Kuhn, Yannic Maus
TL;DR
The paper studies why many LOCAL graph problems have polylogarithmic randomized algorithms but substantially slower deterministic ones. It introduces SLOCAL and P-SLOCAL completeness to analyze this gap, showing that a simple local splitting problem is complete and that efficient deterministic rounding would resolve the broader class of efficient SLOCAL problems. The framework also supports polylogarithmic randomized approximation algorithms for distributed covering and packing programs.
Problem
Many fundamental LOCAL problems have polylogarithmic randomized algorithms but best deterministic algorithms require 2^O(√log n) time, leaving the exponential separation unresolved.
Method
The paper introduces the sequential SLOCAL model and the P-SLOCAL complexity class, then proves completeness results using dependency structures, network decompositions, and low-diameter orderings.
Results
A rudimentary local splitting and rounding problem is P-SLOCAL-complete, so a deterministic polylogarithmic LOCAL algorithm for it would yield such algorithms for all problems in P-SLOCAL.
Takeaways & Limitations
The results identify efficient deterministic approximate rounding of fractional values as the central obstacle to efficient deterministic LOCAL algorithms within the paper’s framework.
Takeaways & Limitations
The framework includes arbitrary local memory in SLOCAL; even one bit of global memory would enable leader election, which cannot be solved locally.
Abstract
from arXiv · showhide
This paper is centered on the complexity of graph problems in the well-studied LOCAL model of distributed computing, introduced by Linial [FOCS '87]. It is widely known that for many of the classic distributed graph problems (including maximal independent set (MIS) and $(Δ+1)$-vertex coloring), the randomized complexity is at most polylogarithmic in the size $n$ of the network, while the best deterministic complexity is typically $2^{O(\sqrt{\log n})}$. Understanding and narrowing down this exponential gap is considered to be one of the central long-standing open questions in the area of distributed graph algorithms. We investigate the problem by introducing a complexity-theoretic framework that allows us to shed some light on the role of randomness in the LOCAL model. We define the SLOCAL model as a sequential version of the LOCAL model. Our framework allows us to prove completeness results with respect to the class of problems which can be solved efficiently in the SLOCAL model, implying that if any of the complete problems can be solved deterministically in $\log^{O(1)} n$ rounds in the LOCAL model, we can deterministically solve all efficient SLOCAL-problems (including MIS and $(Δ+1)$-coloring) in $\log^{O(1)} n$ rounds in the LOCAL model. We show that a rather rudimentary looking graph coloring problem is complete in the above sense: Color the nodes of a graph with colors red and blue such that each node of sufficiently large polylogarithmic degree has at least one neighbor of each color. The problem admits a trivial zero-round randomized solution. The result can be viewed as showing that the only obstacle to getting efficient determinstic algorithms in the LOCAL model is an efficient algorithm to approximately round fractional values into integer values.
1 Introduction & Related Work
The paper frames the randomized–deterministic gap in LOCAL algorithms through the SLOCAL model and P-SLOCAL completeness. Its results identify local rounding and related coordination structures as central barriers to efficient deterministic algorithms.
- The Role of Randomness: Many fundamental LOCAL problems have polylogarithmic randomized algorithms but best deterministic algorithms require 2^O(√log n) time.This gap includes MIS and (Δ+1)-coloring and is a major open question.
- A Complexity-Theoretic Perspective: The paper defines SLOCAL as sequential local computation and studies P-SLOCAL, containing classic problems with efficient randomized but slower deterministic LOCAL algorithms.Processed nodes inspect an r-hop neighborhood and can store information for later nodes.
- Completeness Results: P-SLOCAL-complete problems would yield deterministic polylogarithmic LOCAL algorithms for every problem in P-SLOCAL.The framework also characterizes P-SLOCAL as solvable in randomized polylogarithmic time and deterministic 2^O(√log n) time in LOCAL.
- Completeness Results: Network decompositions and low-diameter orderings provide mechanisms for converting SLOCAL algorithms into distributed algorithms.An ordering is useful when dependency chains remain within small-diameter neighborhoods; every graph has an O(log^2 n)-diameter ordering.
- Completeness Results: Local splitting is P-SLOCAL-complete despite admitting a zero-round randomized solution when constrained-side degrees are sufficiently large.The results cover λ-local splitting and weak local splitting for polylogarithmic degree ranges.
- Completeness Results: The paper interprets coarse fractional-to-integer rounding as the remaining obstacle to efficient deterministic LOCAL algorithms.Efficient deterministic coarse rounding would place classic LOCAL problems such as MIS and (Δ+1)-coloring in P-LOCAL.
2 Computational Models and Complexity Classes
The paper formalizes LOCAL and SLOCAL computation, including their deterministic and randomized complexity classes, and relates sequential locality to distributed locality. SLOCAL processes nodes in an arbitrary order using bounded-radius neighborhoods, while LOCAL runs synchronous communication rounds.
- LOCAL model: In the LOCAL model, nodes receive local inputs and must produce an admissible output vector through synchronous communication rounds.The running time is the number of rounds until every node completes.
- LOCAL model: In randomized LOCAL algorithms, nodes use private random bits, with fixed running time and an error probability for producing an inadmissible output.The paper focuses on Monte Carlo algorithms.
- SLOCAL model: SLOCAL processes nodes sequentially in any supplied order, allowing each node’s output to depend on a bounded-radius neighborhood and previously stored local states.Its locality is the maximum queried radius over all nodes and all processing orders.
- SLOCAL model: Classic problems including MIS, (∆ + 1)-vertex coloring, edge coloring, and maximal matching have SLOCAL locality O(1).This reflects problems where locally valid partial solutions can be extended using local knowledge.
- SLOCAL model: Writing to nearby nodes’ memory changes locality from R to at most r + R, so nearby-write algorithms can be converted to own-memory algorithms.Here r is the write radius and r ≤ R.
- SLOCAL model: For k ≤ polylog n phases, a k-phase SLOCAL algorithm can be transformed into a single-phase algorithm, preserving polylogarithmic locality up to the stated transformation bound.The paper introduces this equivalence through Lemma 2.2.
- Complexity classes: The classes LOCAL(t), RLOCAL_ε(t), SLOCAL(t), and RSLOCAL_ε(t) collect deterministic or randomized problems solvable within the corresponding locality or runtime bounds.The framework uses runtime and error functions depending on the number of vertices.
- Complexity classes: LOCAL algorithms are contained in SLOCAL algorithms because an SLOCAL algorithm can first collect the corresponding-radius neighborhood and then compute the LOCAL output.This yields LOCAL(t(n)) ⊆ SLOCAL(t(n)) and the analogous randomized inclusion.
3 Low Diameter Ordering & Network Decomposition
This section establishes low-diameter orderings and network decompositions as P-SLOCAL-hard problems. The reduction simulates sequential local algorithms by ensuring dependency chains fit inside bounded neighborhoods.
- Low-diameter orderings: Computing a d(n)-diameter ordering is P-SLOCAL-hard for every d(n) = log^O(1) n.The ordering is used to organize dependencies arising from a sequential local algorithm.
- Low-diameter orderings: An ℓ-low-diameter ordering of G^r confines every relevant monotonically increasing dependency chain to the ℓ-neighborhood of the node being processed.This lets nodes collect the information needed to simulate the SLOCAL computation locally.
- Network decomposition: Network decompositions directly imply low-diameter orderings and therefore suffice to simulate polylogarithmic SLOCAL algorithms.This explains why decomposition algorithms underlie deterministic solutions for many P-SLOCAL problems.
- Network decomposition: Computing a (polylog n, polylog n)-network decomposition is P-SLOCAL-hard.The result follows from the relationship between network decompositions and low-diameter orderings.
- Completeness proof: The completeness of low-diameter orderings and network decompositions adapts a deterministic sequential decomposition algorithm to the SLOCAL model.The paper attributes the adaptation to the decomposition algorithm of [LS93].
- Deterministic complexity: The section connects the construction to prior network-decomposition algorithms and records deterministic LOCAL round bounds for suitable decompositions.The cited statements include bounds of the form 2^O(√log n) and O rounds for a constant c.
4 Overview of Local Splitting Completeness Proof
The local-splitting completeness proof proceeds through two reductions: network decomposition to conflict-free multicoloring, then conflict-free multicoloring to local splitting. The construction also explains why local splitting lies in P-SLOCAL.
- Proof overview: The proof establishes P-SLOCAL-completeness for local splitting by showing membership in P-SLOCAL and reducing a known complete problem to it.The reduction first uses conflict-free multicoloring and then network decomposition.
- Conflict-free multicoloring reduction: A λ-local splitting oracle yields a polylogarithmic-color conflict-free multicoloring, with weak local splitting obtained through a further reduction.The oracle parameter is λ = 1/polylog n.
- Conflict-free multicoloring reduction: For hypergraphs of polylogarithmic rank, deterministic polylogarithmic-time defective coloring supplies the conflict-free multicoloring step.The construction assigns new colors to remove low-rank hyperedges before invoking local splitting.
- Conflict-free multicoloring reduction: Each reduction phase removes low-rank hyperedges using conflict-free colors, then applies λ-local splitting so every remaining hyperedge retains at least one red node before blue nodes are removed.Since remaining hyperedges have rank greater than δ = 1/λ, the splitting guarantee ensures a red node remains.
- Network decomposition reduction: The reverse construction uses conflict-free multicoloring on almost uniform hypergraphs formed from node-centered balls to compute a network decomposition.The reduction creates O(log(n)/ε) hypergraphs and groups balls by comparable sizes.
- Weak local splitting: Weak local splitting is in P-SLOCAL because a polylogarithmic network decomposition lets each cluster choose a local red/blue coloring that makes sufficiently large neighborhoods bichromatic.The construction assumes each U-node has degree c ln^2 n for sufficiently large c.
5 Completeness of Conflict-Free Multicoloring
Conflict-free multicoloring is both easy with zero-round randomization and complete for P-SLOCAL under the stated hypergraph conditions. The completeness proof reduces network decomposition to multicoloring and constructs a matching SLOCAL algorithm.
- Problem definition: A q-color conflict-free multicoloring assigns each node a nonempty color set so every hyperedge has a color appearing on exactly one node.The section studies this problem for almost uniform hypergraphs.
- Problem definition: Almost uniform hypergraphs have edge sizes between k and (1 + ε)k for some k and fixed 0 < ε < 1.This size condition is the regularity assumption used in the completeness theorem.
- Completeness result: Conflict-free multicoloring with polylogarithmic colors in almost uniform hypergraphs with polynomially many hyperedges is P-SLOCAL-complete.This is the section’s main theorem.
- Randomized upper bound: An O(log n)-color conflict-free multicoloring has a zero-round randomized LOCAL algorithm for almost uniform hypergraphs with polynomially many hyperedges.The random assignment succeeds with high probability.
- Hardness: The hardness direction reduces computing a (polylog n, polylog n)-network decomposition to conflict-free multicoloring.The reduction uses O(log n/ε) oracle iterations on almost uniform hypergraphs.
- Hardness: The reduction builds O(log n/ε) almost uniform hypergraphs from balls around vertices, simulates each hypergraph round within O(q log n/ε) rounds, and obtains a (2R, qℓ)-decomposition.Each hypergraph uses q-color multicoloring with disjoint color ranges.
- SLOCAL upper bound: An SLOCAL algorithm computes an O(log n)-color conflict-free multicoloring in polylogarithmic locality.It uses O(log n) phases, each reducing the number of unresolved hyperedges by a constant factor.
- SLOCAL upper bound: At least a constant fraction of the remaining hyperedges receive unique colors in each phase, so O(log n) phases suffice.Vertices without a color receive a default color at the end.
6 Completeness of Local Splitting
This section proves that local splitting problems are P-SLOCAL-complete, despite admitting trivial zero-round randomized solutions. The proof uses reductions through conflict-free multicoloring and establishes both hardness and efficient SLOCAL algorithms.
- Problem definition: Local splitting asks for a red-blue coloring of V that gives each node in U neighbors of both colors, either proportionally or at least once.λ-local splitting requires at least floor(λ·d(v)) neighbors of each color; weak local splitting requires one neighbor of each color.
- Randomized baseline: Zero-round random coloring solves local splitting with high probability when U-nodes have sufficiently large degree.Each node in V independently chooses red or blue with probability 1/2; the guarantee follows from Chernoff bounds and a union bound.
- Proof strategy: The hardness proof reduces conflict-free multicoloring to local splitting through two polylogarithmic reductions.The intermediate constructions use hypergraph multicoloring and then reduce λ-local splitting to weak splitting for bounded-degree bipartite graphs.
- Supporting construction: The conflict-free multicoloring procedure uses log^O(1) n phases because the associated multigraph degree decreases geometrically.Each phase applies defective coloring, removes uniquely colored hyperedges, and reduces the maximum degree by at least a factor of two.
- Completeness results: λ-local splitting is P-SLOCAL-hard for every λ = 1/polylog n, while weak local splitting remains P-SLOCAL-complete at polylogarithmic degrees.The completeness results apply to λ-local splitting with U-degrees at least c ln^2 n and to weak splitting with degrees between δ/2 and δ.
7 Approximating Covering and Packing Integer Linear Programs
This section applies the SLOCAL framework to covering and packing integer linear programs. It gives polylogarithmic-locality deterministic SLOCAL approximations and transfers them to randomized LOCAL algorithms.
- General framework: Covering and packing ILPs receive deterministic SLOCAL (1 + ε)-approximations in complexity O(poly(log n/ε)).The framework is presented through maximum independent set and minimum dominating set, with extensions to general weighted and coefficient-bounded cases.
- Maximum independent set: Maximum independent set has a deterministic SLOCAL (1 + ε)-approximation with complexity O(poly(log n/ε)).A ball-growing argument selects locally near-stable-radius regions, solves each selected ball, and removes a slightly larger neighborhood.
- Maximum independent set: The corresponding randomized LOCAL algorithm computes a high-probability (1 + ε)-approximation to maximum independent set in O(poly(log n/ε)) complexity.The paper identifies this as its first such high-probability approximation guarantee for maximum independent set.
- Minimum dominating set: Minimum dominating set has a deterministic SLOCAL (1 + ε)-approximation with complexity O(poly(log n/ε)).The construction uses a ball-growing argument that selects a small dominating set for an expanded local region and removes the central ball.
8 On The Power of the Sequential LOCAL Model
This section shows that randomized SLOCAL algorithms with polylogarithmic locality can be simulated in the randomized LOCAL model with only a negligible increase in error. Polylogarithmically many SLOCAL phases do not materially enlarge the class.
- Model comparison: The SLOCAL model is stronger than LOCAL because nodes are processed sequentially and retain state visible to later nodes.Its apparent power includes constant-locality solutions for classic problems such as MIS, (Δ + 1)-coloring, and maximal matching.
- Simulation result: Polylogarithmic-locality randomized SLOCAL algorithms can be simulated in randomized LOCAL with error increase of 1/poly(n).The formal inclusion is P-RSLOCAL_ε ⊆ P-RLOCAL_{ε+1/poly(n)}.
- Simulation method: The simulation constructs a network decomposition of the relevant power graph and uses its cluster ordering to reproduce the SLOCAL execution.Clusters of the same color are sufficiently separated, allowing each cluster to gather the information needed for local simulation.
- Generalization: The simulation extends to randomized time bounds t(n) satisfying t(n) ≥ log n, with the same additive 1/poly(n) error increase.The resulting inclusion is RSLOCAL_ε(t^O(1)(n)) ⊆ RLOCAL_{ε+1/poly(n)}(t^O(1)(n)).
- Multiple phases: Allowing polylogarithmically many SLOCAL phases does not change the polylogarithmic-locality class significantly.A k-phase algorithm can be converted to a single-phase algorithm with locality equal to the sum of its phase localities.
9 Low Diameter Ordering & Network Decomposition are in P-SLOCAL
This section places network decomposition and low-diameter ordering inside P-SLOCAL. It adapts sequential ball-growing constructions to obtain polylogarithmic-locality SLOCAL algorithms and proves decomposition completeness.
- Network decomposition: A network decomposition partitions vertices into bounded-diameter clusters whose cluster graph is properly colored.The decomposition is organized into blocks, with clusters in the same block nonadjacent.
- Sequential construction: Sequential ball growing repeatedly selects a ball, removes its boundary, and forms nonadjacent clusters until all vertices are covered.Each block removes a constant fraction of remaining vertices, so O(log n) blocks suffice.
- Construction guarantees: The resulting clusters have weak diameter at most O(log^2 n) and clusters in the same block are nonadjacent.The diameter bound follows from the selected ball radius, while boundary removal prevents adjacency within a block.
- SLOCAL algorithms: Network decomposition can be computed in P-SLOCAL, including a single-phase formulation.The deterministic sequential construction is adapted to SLOCAL with polylogarithmic locality, and multi-phase execution can be compressed into one phase.
- Low-diameter ordering: Computing a polylogarithmic-diameter ordering is also in P-SLOCAL.The result follows from the network-decomposition construction and the associated ordering observation.