On the complexity of computing Strahler numbers

This paper establishes that computing the Strahler number of a binary tree is complete for uniform $\mathsf{NC}^1$ when the tree is given as a term, while determining variants for pointer structures, DAGs, and tree straight-line programs, and proving that deciding if a context-free grammar produces a derivation tree with a Strahler number of at least $k$ is $\mathsf{P}$-complete (or $\mathsf{PSPACE}$-complete for acyclic trees).

The Gist

The Big Picture: What is a Strahler Number?

Imagine you are looking at a river system. You have a tiny stream that flows into a slightly bigger stream, which flows into a river, which eventually becomes a massive waterway.

In the 1940s, scientists realized that if you map these rivers as a tree (where the big river is the top and the tiny streams are the leaves), you can assign a "rank" to every part of the system. This is called the Strahler number.

• Rank 0: A tiny, headwater stream with no other streams feeding into it.
• Rank 1: Two Rank 0 streams joining together.
• Rank 2: Two Rank 1 streams joining together.
• The Rule: If two streams of the same rank join, the resulting river gets a rank one step higher. If a Rank 2 stream joins a Rank 1 stream, the result stays Rank 2 (the bigger one dominates).

This concept isn't just for rivers. In computer science, it measures how "deep" or "complex" a calculation is. Think of it as the minimum number of workers (or registers) you need to solve a math problem without running out of space.

The Problem: How Hard is it to Calculate?

The paper asks a simple question: How much computing power does it take to figure out the Strahler number of a given tree?

The authors looked at this problem under different "lenses" (input formats) to see how the difficulty changes.

1. The "Textbook" Version (Term Representation)

Imagine the tree is written out as a long string of text, like a recipe: b(b(a, a), b(a, a)).

• The Finding: Calculating the rank here is moderately hard but very parallelizable.
• The Analogy: Imagine a library where you have a million librarians. If you give them this text, they can all work on different parts of the sentence at the same time to figure out the answer very quickly. The paper proves this task belongs to a class called NC1. It's fast if you have many processors, but it's not "instant" (like flipping a light switch).

2. The "Map" Version (Pointer Representation)

Imagine the tree isn't a string, but a physical map where every node has a pointer (a sticky note) telling you where its children are.

• The Finding: This is easier.
• The Analogy: If you have a map with clear arrows, you can walk through it with a single person (a standard computer) using very little memory (logarithmic space). It's like following a treasure map with a single flashlight; you don't need a team, you just need to be careful.

3. The "Compressed" Version (DAGs and TSLPs)

Sometimes, trees are huge. To save space, we compress them. Imagine a "Choose Your Own Adventure" book where, instead of rewriting the same chapter every time a character makes a choice, you just say "Go to Chapter 5." This is a Directed Acyclic Graph (DAG) or a Tree Straight-Line Program (TSLP).

• The Finding: This is much harder.
• The Analogy: Because the tree is compressed, the "real" tree is exponentially larger than the file size. To find the Strahler number, the computer has to mentally "unzip" the file.
  • If the tree is given as a DAG, the problem is P-complete. This means it's as hard as the hardest problems solvable in a reasonable amount of time. It's like trying to solve a massive jigsaw puzzle where the picture is hidden inside a tiny box; you have to do a lot of work, and you can't really speed it up by adding more workers.
  • If the tree is a TSLP, it's even trickier, falling into NL-complete or PSPACE-complete depending on the specific rules.

The Grammar Twist: Context-Free Grammars

The paper also looked at trees that are generated by Context-Free Grammars (rules that build sentences, like in a language).

• The Question: Can a set of grammar rules produce a tree with a Strahler number of at least $k$?
• The Finding:
  • If we allow the tree to loop back on itself (infinite recursion), the problem is P-complete (hard, but solvable).
  • If we restrict the tree so it cannot loop (acyclic), the problem jumps to PSPACE-complete.
  • The Analogy: Imagine a maze.
    • P-complete: You can solve the maze, but it might take a long time.
    • PSPACE-complete: The maze is so complex that to solve it, you might need to remember every single step you've ever taken, requiring a massive amount of memory. It's like trying to solve a maze where the walls move based on your entire history of moves.

Why Does This Matter?

The authors aren't just playing with math for fun. They are trying to find the exact "speed limit" of these calculations.

• For Engineers: If you know a problem is NC1, you know you can build a super-fast parallel computer to solve it.
• For Theorists: If a problem is P-complete, you know you shouldn't waste time trying to make it run in parallel; you should focus on optimizing the single-threaded algorithm.
• For Memory: If a problem is PSPACE-complete, you know you need a lot of memory to solve it, and you can't just throw more processors at it to make it faster.

Summary of the "Difficulty Ladder"

1. Easy (Logspace): Walking a physical map (Pointer representation).
2. Medium (NC1): A massive team of workers reading a text book (Term representation).
3. Hard (P-complete): Unzipping a compressed file to solve a puzzle (DAG representation).
4. Very Hard (PSPACE-complete): Solving a maze where you must remember every step forever (Acyclic derivation trees in complex grammars).

The paper's main achievement is mapping exactly where the Strahler number calculation sits on this ladder for every possible way you might present the tree to a computer. They proved that the "textbook" version is perfectly balanced for parallel computing, while the "compressed" versions get significantly harder, requiring more time or memory.

Technical Summary

Technical Summary: On the Complexity of Computing Strahler Numbers

Problem Definition

The paper investigates the computational complexity of determining the Strahler number (also known as the Horton-Strahler number) of binary trees. The Strahler number, denoted $st(t)$, is a parameter defined recursively for a binary tree $t$:

• If $t$ is a single leaf, $st(t) = 0$.
• If $t$ has left and right subtrees $t_1$ and $t_2$, then:
  • $st(t) = st(t_1) + 1$ if $st(t_1) = st(t_2)$.
  • $st(t) = \max\{st(t_1), st(t_2)\}$ if $st(t_1) \neq st(t_2)$.

This parameter is algebraically equivalent to evaluating a tree in the Strahler algebra $(\mathbb{N}, s, 0)$, where the binary operation $s(x, y)$ is defined as $x+1$ if $x=y$ and $\max(x, y)$ otherwise. While a straightforward bottom-up algorithm computes this in linear time, the paper seeks to pinpoint the precise parallel complexity (circuit complexity) and space complexity of the problem under various input representations.

The study considers four primary input representations for the tree $t$:

1. Term Representation: The tree is given as a string (e.g., $b(b(a,a), a)$).
2. Pointer Representation: The tree is given as an adjacency list or matrix.
3. DAG Representation: The tree is given as a succinct Directed Acyclic Graph (DAG) whose unfolding is the tree.
4. TSLP Representation: The tree is given by a Tree Straight-Line Program (a compressed grammar-based representation).

Additionally, the paper examines the complexity of deciding whether a Context-Free Grammar (CFG) in Chomsky Normal Form (CNF) produces a derivation tree with a Strahler number $\ge k$, both for general and acyclic derivation trees.

Methodology

The authors employ techniques from circuit complexity, formal language theory, and algebraic tree evaluation.

1. Upper Bounds and Tree Balancing

To establish upper bounds for the term representation, the authors utilize Tree Straight-Line Programs (TSLPs).

• Balancing: They first transform the input tree $t$ into a TSLP of logarithmic depth using a result from [29]. This "balances" the tree, reducing the depth from potentially linear to logarithmic.
• Functional Algebra Analysis: A core technical contribution is characterizing the unary linear term functions computed by contexts within the TSLP under the Strahler algebra. They prove that any context $B$ computes a function $st_B: \mathbb{N} \to \mathbb{N}$ of the form $[\ell, h]$, defined as:
  $$[\ell, h](x) = \begin{cases} h & \text{if } x < \ell \\ h+1 & \text{if } \ell \le x \le h \\ x & \text{if } x > h \end{cases}$$
• Circuit Construction: Using the closure properties of these functions under composition (Lemma 3.2), they construct a Boolean circuit of logarithmic depth and polynomial size that decides if $st(t) \ge k$. This places the problem in uniform NC1 ($uNC1$).

2. Lower Bounds and Reductions

• NC1-Hardness: The authors reduce the Boolean Formula Value Problem (known to be $uNC1$-complete) to the Strahler number problem. They simulate Boolean AND and OR operations using specific Strahler algebra expressions that preserve the logic of the formula while mapping truth values to specific integer ranges.
• P-Hardness: For succinct representations (DAGs and TSLPs), they reduce the Monotone Circuit Value Problem (P-complete) to the Strahler number problem.
• Space Complexity: For fixed $k$, they analyze the problem using alternating logspace machines and reductions from graph accessibility problems to determine membership in classes like $L$, $NL$, and $PSPACE$.

Key Contributions and Results

1. Complexity for Term and Pointer Representations

• Term Representation: The problem of deciding $st(t) \ge k$ is $uNC1$-complete. This establishes that the problem can be solved in polylogarithmic time with polynomial processors, but likely not in logarithmic space (unless $L = uNC1$).
• Pointer Representation: The problem is $L$-complete (deterministic logspace). This is a significant distinction, showing that the representation format drastically changes the complexity class.
• Fixed $k$:
  • For term representation, $st(t) \ge k$ is $uTC0$-complete for $k \ge 4$.
  • For pointer representation, it is $L$-complete for $k \ge 3$.

2. Complexity for Succinct Representations (DAG and TSLP)

• General Case: Deciding $st(t) \ge k$ for trees given by DAGs or TSLPs is P-complete.
• Fixed $k$:
  • For DAGs, the problem is $L$-complete for $k \ge 3$.
  • For TSLPs, the problem is $NL$-complete for $k \ge 2$.

3. Complexity for Context-Free Grammars

The paper analyzes the problem of whether a CNF-grammar $G$ generates a derivation tree with $st(t) \ge k$.

• General Derivation Trees: The problem is P-complete for any $k \ge 1$. The proof involves a fixpoint iteration to compute the maximal Strahler number for each nonterminal.
• Acyclic Derivation Trees:
  • If $k$ is part of the input, the problem is PSPACE-complete. This is shown via a reduction from Quantified Boolean Formulas (QBF), where the grammar simulates the quantifier structure.
  • If $k$ is fixed ($k \ge 2$), the problem is NP-complete. This is shown via a reduction from Exact 3-Hitting Set.

4. Space Complexity Refinement

The paper provides a refined space complexity analysis, showing that the Strahler number of a tree with $n$ leaves can be computed in $O(\log n \log \log n)$ space. By using delta encoding for the sequence of Strahler numbers during a depth-first traversal, they reduce this to $O(\log n)$ space, confirming the problem's membership in $L$ for pointer representations.

Significance and Claims

The paper claims to resolve the precise complexity of computing Strahler numbers, a parameter with applications in hydrology, register allocation, and formal language theory.

• Precision: It moves beyond the known fact that the problem is in $NC$ to pinpoint the exact class ($uNC1$) for term representations and $L$ for pointer representations.
• Representation Sensitivity: It highlights how the choice of input representation (term vs. pointer vs. DAG/TSLP) shifts the problem across the complexity hierarchy from $uNC1$ to $L$ to $P$ and $PSPACE$.
• Algebraic Insight: The characterization of unary linear term functions in the Strahler algebra (the $[\ell, h]$ functions) is presented as a necessary tool for efficient tree balancing and evaluation, analogous to affine functions in other algebras.
• Grammar Complexity: It establishes the hardness of analyzing Strahler numbers in the context of CFGs, linking the problem to the intersection non-emptiness problem for group DFAs and pushdown systems.

The authors conclude by noting that while their $NC1$ algorithm for binary trees is robust, extending these results to unranked trees or the max-plus semiring remains an open challenge.