On the Volume Complexity of LCLs*

Will Rosenbaum
Max Planck Institute for Informatics

Jukka Suomela
Aalto University

* Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems [arXiv:1907.08160]

Overview

  1. LCLs in the LOCAL Model
  2. Query Model and Volume Complexity
  3. Complexity Landscape for Volume
  4. Open(?) Questions

I. LCLs in the LOCAL Model

Context

  • consider family graphs $\mathcal{G}$ with maximum degree at most $\Delta$ (constant)
  • an instance is a graph $G \in \mathcal{G}$ with a vertex labeling $\mathcal{L}$ from a finite alphabet
  • want to find a valid output labeling $\mathcal{L}'$ that solves problem $\Pi$ on input $(G, \mathcal{L})$
  • $\Pi$ is a locally checkable labeling problem (LCL) if a solution is globally valid $\iff$ it is valid on an $O(1)$ neighborhood of each node
  • e.g., $k$ coloring, maximal matching, maximal independent set,...
  • LOCAL model: in $T$ rounds, every node sees its distance $T$ neighborhood

Distance Complexity Landscape

distance complexity classes

II. Query Model and Volume Complexity

Query Model

  • each $v \in V$ represents a processor
  • $v$ maintains set $V_v$ of visited nodes, initially $V_v = \{v\}$
  • $v$ adaptively queries $G$
  • for $u \in V_v$, $\mathrm{query}(u, j)$ returns
    • identity, input, and degree of $u$'s $j$th neighbor $w$
    • $w$'s random bits (for randomized algorithms)
    • $v$ sets $V_v \leftarrow V_v \cup \{w\}$

Volume of algorithm $A$: maximum $|V_v|$ over all nodes $v$, graphs, inputs on $n$ nodes

Note. similar to LCA model

Questions

What are the possible volume complexities of LCL problems?

How are volume and distance complexities related?

What is the role of randomness in the volume model?

III. Main Results: Volume Complexity Landscape

Preliminary Observations

Observation 1. If $\Pi$ has round complexity $T(n)$ in the LOCAL model, then its volume complexity $R(n)$ satisfies $$ T(n) \leq R(n) \leq \Delta^{O(T(n))} $$

Observation 2. If $\Pi$ has randomized volume complexity $R(n)$, then its deterministic volume complexity $D(n)$ satisfies $D(n) \leq R(2^{n^2})$.

  • proof from [Chang, Kopelowitz, Pettie 2019] for LOCAL model carries over to volume model

Uncharted Terrain

uncharted terrain

Summary of Results: New Classes

Problem R-DIST D-DIST R-VOL D-VOL
LeafColoring $\Theta(\log n)$ $\Theta(\log n)$ $\Theta(\log n)$ $\Theta(n)$
BalancedTree $\Theta(\log n)$ $\Theta(\log n)$ $\Theta(n)$ $\Theta(n)$
Hier-THC($k$) $\Theta(n^{1/k})$ $\Theta(n^{1/k})$ $\tilde\Theta(n^{1/k})$ $\tilde\Theta(n)$
Hybrid-THC($k$) $\Theta(\log n)$ $\Theta(\log n)$ $\tilde\Theta(n^{1/k})$ $\tilde\Theta(n)$
HH-THC($k$, $\ell$) $\Theta(n^{1/\ell})$ $\Theta(n^{1/\ell})$ $\tilde\Theta(n^{1/k})$ $\tilde\Theta(n)$
uncharted terrain

LeafColoring

  • Input: each $v \in V$ gets
    • parent $P(v)$, left child $LC(v)$, right child $RC(v)$
      (port #s or $\perp$)
    • input color $\chi_{\mathrm{in}}(v) \in \{R, B\}$
  • Output: a color $\chi_{\mathrm{out}}(v) \in \{R, B\}$
  • Validity: Call $v$ internal if port labels are pair-wise distinct and $v = P(RC(v)) = P(LC(v))$.
    • $v$ not internal $\implies$ $\chi_{\mathrm{out}}(v) = \chi_{\mathrm{in}}(v)$
    • $v$ internal $\implies$ $\chi_{\mathrm{out}}(v) \in \{\chi_{\mathrm{out}}(RC(v)), \chi_{\mathrm{out}}(LC(v))\}$

LeafColoring Example

a graph a graph a graph

Input graph, port numbers shown for vertex $v$

Input labeling and induced pseudo-forest ($P(v) = 4$, $LC(v) = 1$, $RC(v) = 3$)

Valid output labeling

Analysis of LeafColoring

  • Algorithm:
    • each internal $v$ uses private randomness to choose a child
    • follow path of "chosen children" to a leaf *
    • output color of leaf
  • W.H.P. all paths to leaves are of length $O(\log n)$
  • $\Omega(\log n)$ distance is necessary to see leaf
  • $\Omega(n)$ volume is necessary for deterministic algorithms

* have to deal with cycles, but whatever

BalancedTree

  • Input: each $v \in V$ gets
    • parent $P(v)$, left child $LC(v)$, right child $RC(v)$
      (port #s or $\perp$)
    • left neighbor $LN(v)$, right neighbor $RN(v)$
  • Output: $(X, P)$ where $X \in \{B, U\}$ (balanced/unbalanced), $P$ is port number
  • Compatibility: $v \in V$ is compatible if some locally checkable conditions on input labeling are satisfied
    • all nodes compatible $\iff$ parent/child edges form balanced binary tree $+$ "lateral" edges
  • Validity:
    • $v$ not compatible $\implies$ $v$ outputs $(U, \perp)$
    • compatible "leaves" output $(B, P(v))$
    • internal nodes output $(B, P(v))$ $\iff$ both children do
    • internal nodes output $(U, \cdot)$ where $\cdot$ is child outputting $(U, \cdot)$
  • Global Interpretation:
    • if all nodes $v$ output $(B, P(v))$, then parent/child edges form a balanced binary tree with compatible lateral edges
    • if some node $v$ is incompatible, then all ancestors of $v$ output $(U, \cdot)$

Analysis of BalancedTree

  • for each $v$, suffices to see all descendants within distance $d(v, w)$ where $w$ is nearest leaf below $v$
    • $\implies O(\log n)$ distance suffices
  • for root of balanced binary tree, must examine all leaves to find incompatible node
    • $\implies \Omega(n)$ volume necessary

BalancedTree Example

uncharted terrain

IV. Open(?) Questions

More Complexity Classes?

  1. Are there LCLs with deterministic volume complexity in $\omega(\log^* n) \cap o(n)$?
  2. Are there LCLs with randomized volume complexity in $\Omega(\log \log n) \cap o(\log n)$?
    • What is the (randomized) volume complexity of Sinkless Orientation?
  3. Are there LCLs with randomized volume complexity $\sim n^{\alpha}$ for $\alpha \neq 1/k$?

Type of Randomness?

Could consider (at least) $3$ types of randomness:

  • public randomness all nodes have access to same random string (e.g. LCAs)
  • private randomness each node has own independent random string
    • querying $v$ reveals $v$'s randomness
  • secret randomness each node has own independent random string
    • querying $v$ does not reveal $v$'s randomness

Question. What is the relative power of these random models?

Complexity with Limited Bandwidth?

Question.What do complexity classes look like in CONGEST model?

  • in each round, nodes can send $B (= O(\log n))$ bit messages to each neighbor
  • preliminary observations in our paper

Question. Is there an LCL with volume complexity $R(n)$ and CONGEST complexity $\Delta^{\Omega(R(n))}$?

Thank You!

arXiv:1907.08160

full paper here