Technical Summary: Algebraic Expressions for Directed Grid Graphs with Diagonal Edges

1. Problem Statement

This research investigates the construction of compact formal algebraic expressions (specifically, path polynomials) for two families of edge-labeled, two-terminal directed acyclic graphs (st-dags): Directed Triangulated Grid Graphs (TGGs) and Directed King Graphs.

In these graphs:

• TGGs consist of an $m \times n$ grid with horizontal, vertical, and down-right diagonal edges.
• King Graphs extend TGGs by adding up-right diagonal edges, allowing movement in all eight directions (like a chess king).

The objective is to represent the canonical path polynomial $P_G$, defined as the formal sum of all source-to-target path products in the free noncommutative semiring $\mathbb{N}\langle X_G \rangle$, using an algebraic expression of minimal length. The length is measured by the total number of label occurrences in an explicit formula (a tree representation, not a shared DAG).

The paper addresses the gap between simple backtracking constructions, which often yield exponential or high-degree polynomial lengths, and the need for efficient, quasi-linear representations, particularly for fixed depth $m$ and variable size $n$.

2. Methodology

The authors employ a combination of algebraic analysis, recursive decomposition algorithms, and complexity theory techniques.

2.1 Recursive Construction Algorithms

Three primary algorithmic approaches are analyzed:

1. Backtracking Method: A universal method accumulating subexpressions at vertices. For TGGs, it processes the graph from the target back to the source. For King graphs, it must handle complex subgraph geometries (pentagons, trapezoids) caused by upward-moving edges.
2. Geometric Decomposition: A divide-and-conquer approach that splits the graph vertically (or horizontally) into subgraphs connected by "separator" edges. This method factors out common subexpressions to reduce length. Variants include:
   • Basic Decomposition: Splits the graph at the middle column.
   • Improved Decomposition: Applies specific simplifications for small sizes ($n=2, 3$) and boundary cases.
   • Alternating Decomposition: Dynamically chooses the split direction (vertical or horizontal) based on which dimension is larger, utilizing a canonical transposition map to maintain symmetry.
3. Column-Transfer (Algebraic Branching Program) Method: Specifically for King graphs, this method models the graph as a sequence of $m \times m$ transfer matrices. The path polynomial is computed as a product of these matrices, simulated by formulas using a divide-and-conquer strategy.

2.2 Lower Bound Techniques

To prove optimality, the paper utilizes several restriction and projection techniques:

• Edge-Occurrence Bounds: Establishing that every edge label must appear at least once.
• Homomorphism Projections: Mapping edge labels to binary words to transform the path polynomial into regular languages (e.g., binomial languages $B_{N,k}$ or parity languages $P^\varepsilon_N$).
• Cut Substitution Theorem: Demonstrating that setting edge labels to 0 corresponds to finding minimal cuts, linking path expressions to network reliability.
• Iterated Matrix Multiplication (IMM): Reducing the King graph problem to the known complexity of computing iterated matrix products to derive depth-restricted lower bounds.

3. Key Contributions and Results

3.1 Directed Triangulated Grid Graphs (TGGs)

• Backtracking Performance: Produces expressions of length $O_m(n^m)$. While polynomial, the degree grows with depth $m$.
• Decomposition Performance: The decomposition methods (basic, improved, and alternating) achieve a length of $O_m(n \log^{m-1} n)$.
• Optimality:
  • For depths $m \in \{1, 2, 3, 4\}$, the bound $O_m(n \log^{m-1} n)$ is proven to be globally optimal ($\Theta_m(n \log^{m-1} n)$) via a projection to binomial languages.
  • For any fixed depth $m$, the bound is proven optimal within the specific balanced column-interval decomposition model.
  • The paper conjectures that the global optimality holds for all fixed $m$ if the corresponding lower bound for binomial languages holds.

3.2 Directed King Graphs

• Backtracking Performance: The method yields expressions of exponential length in $n$ even for depth $m=2$ (specifically $\Omega(3^n)$). This highlights the structural complexity introduced by upward-moving edges.
• Geometric Decomposition: Achieves a length of $O_m(n^{\log_2(4m-2)})$.
• Column-Transfer (ABP) Method: By interpreting the graph as a fixed-width Algebraic Branching Program (ABP), the upper bound is improved to $O_m(n^{1+\log_2 m})$.
• Lower Bounds:
  • Unrestricted: Using parity-language restrictions, the paper proves a lower bound of $\Omega(n^2)$ for all $m \ge 2$. For $m=2$, this matches the upper bound, establishing $\Theta(n^2)$.
  • Depth-Restricted: For $m > 2$, the paper establishes depth-restricted lower bounds based on iterated matrix multiplication, showing that polynomial-length formulas require product-depth $\Omega(\log n)$.
  • Gap: A gap remains between the unrestricted lower bound ($\Omega(n^2)$) and the best upper bound ($O_m(n^{1+\log_2 m})$) for $m > 2$.

3.3 Structural and Algebraic Insights

• Symmetry: The paper establishes a "canonical transposition" $\tau_{m,n}$ that maps $T_{m,n}$ to $T_{n,m}$ and preserves expression lengths algorithmically, not just structurally.
• Reliability Connection: Theorem 4 formally links minimal source-target cuts to the annihilation of the path polynomial via zero substitutions. This provides an algebraic bridge between path compression and minimal failure enumeration.

4. Significance and Claims

The paper claims significance in the following areas:

1. Resolution of TGG Complexity: It provides the first proof of global optimality for path expressions in triangulated grid graphs up to depth 4 and within a specific recursive model for all depths, resolving the complexity of these non-series-parallel graphs.
2. King Graph Decomposition: It demonstrates that while backtracking fails catastrophically for King graphs (exponential blowup), geometric decomposition and ABP-based methods can recover quasi-polynomial or polynomial efficiency.
3. Algebraic-Reliability Bridge: It explicitly connects the length of path expressions to the enumeration of minimal cuts, suggesting that the complexity of factoring path polynomials is intrinsically linked to the complexity of network reliability analysis.
4. Methodological Rigor: The work distinguishes between formula length (explicit tree size) and circuit/DAG size (shared subexpressions), clarifying that the presented bounds apply to explicit formulas.

The authors note that the results are modest regarding the "unrestricted" global optimality for King graphs with $m > 2$, acknowledging the gap between the $\Omega(n^2)$ lower bound and the $O(n^{1+\log_2 m})$ upper bound as an open problem requiring sharper formula-complexity techniques.