Edit distance for strings is a solved problem: $O(nm)$ dynamic programming, textbook material. Edit distance for tables is NP-hard. The jump from polynomial to intractable happens the moment you go from one dimension to two.

Why? The answer is a single number: treewidth. The constraint graph underlying a 1D edit distance computation is a path (treewidth 1). The constraint graph for a 2D table is a grid (treewidth $\min(\text{rows}, \text{cols})$). Every complexity result in this post — polynomial for sequences, NP-hard for tables, fixed-parameter tractable when columns are bounded — falls out of this one graph invariant.

This post accompanies tate, a self-contained structured diff library in Rust. I’ll formalize table edit distance, prove it’s a metric, prove it’s NP-hard for any positive cost model (not just a specific one), and identify the treewidth boundary that separates tractable from intractable.

1. The Treewidth Lens

1.1 Edit Distance as a Constraint Graph

Computing edit distance between two structures can be encoded as a constraint satisfaction problem. The variables are the matching decisions: which elements of the old structure correspond to which elements of the new. The constraints enforce consistency: matched elements must agree on their values, and the matching must respect order.

These variables and constraints form a constraint graph — vertices are variables, edges connect variables that share a constraint. The treewidth of this graph controls the complexity of finding the optimal matching.

1.2 What Is Treewidth?

Treewidth measures how tree-like a graph is. A tree has treewidth 1. A cycle has treewidth 2. A grid of size $r \times c$ has treewidth $\min(r, c)$. Formally, treewidth is defined via tree decompositions: a tree whose nodes (“bags”) are sets of vertices, such that (a) every edge’s endpoints appear together in some bag, and (b) the bags containing any given vertex form a connected subtree. The width is the largest bag size minus 1.

The key theorem that connects treewidth to complexity:

Theorem (standard, cf. Freuder 1990, Robertson-Seymour 1986). Any constraint satisfaction problem on a graph of treewidth $w$, with domain size $d$ and constraint arity $a$, can be solved in $O(d^{a \cdot w} \cdot n)$ time.

For edit distance, the domain is small (match or no-match) and the arity is low (binary constraints between adjacent elements). The exponential factor depends on $w$, not on the input size $n$. When $w$ is small, the problem is tractable. When $w$ is unbounded, it isn’t.

1.3 The Two Cases

1D sequences. Aligning two sequences $A = [a_1, \ldots, a_n]$ and $B = [b_1, \ldots, b_m]$ creates a constraint graph that is essentially a path: $a_i$ must be compared to $b_j$ in a sequential sweep. Treewidth = 1. The $O(nm)$ DP is the treewidth-1 algorithm in disguise.

2D tables. Aligning two tables creates a constraint graph where each cell $(i, j)$ depends on the row alignment of row $i$ and the column alignment of column $j$. This graph is a grid, with treewidth $\min(\text{rows}, \text{cols})$. When both dimensions grow, treewidth grows, and the exponential factor $d^{aw}$ explodes.

Everything that follows is a consequence of this single observation.

2. Solving tw = 1: The 1D Pipeline

Treewidth 1 guarantees polynomial solvability for sequence edit distance. But a naive $O(nm)$ DP table uses $O(nm)$ space — a $300000 \times 300000$ matrix of i32 is 360 GB. Guaranteeing a polynomial solution exists and actually computing it efficiently on large inputs are different engineering problems.

Tate’s lines.rs solves this with a four-stage pipeline. Each stage exploits the path structure that treewidth 1 provides.

2.1 Prefix/Suffix Stripping

Strip matching prefix and suffix lines before diffing. This is $O(\min(n,m))$ and handles the common case (small change in large file) almost entirely — the remaining middle is often tiny.

2.2 Patience Anchoring

Patience diff (Bram Cohen, 2003; adopted by Git in 2009) finds lines that appear exactly once in both sequences (“unique common lines”). These form anchor pairs $(a_i, b_j)$. The longest increasing subsequence of the $b$-coordinates (ordered by $a$-coordinate) gives a maximal in-order set of anchors, computed via patience sorting in $O(k \log k)$.

Each anchor splits the problem into independent sub-problems — the regions between consecutive anchors. For structured documents, unique anchor lines (section headers, row IDs, fixed-format tokens) are abundant, so patience typically reduces a large diff to many small ones.

2.3 Per-Segment Solver

Each anchor-free segment is solved by the appropriate algorithm, chosen by size:

Segment size ($n \cdot m$)AlgorithmTimeSpace
$\leq 2^{22}$ (4M cells)Exact LCS (full DP)$O(nm)$$O(nm)$
$\leq 2^{24}$ (16M cells)Hirschberg$O(nm)$$O(\min(n,m))$
$> 2^{24}$Block replacement bailout$O(n+m)$$O(1)$

Hirschberg’s algorithm (1975) achieves the same optimal result as full DP but in linear space. It recursively splits $A$ in half, finds the optimal split point in $B$ via two rolling-row LCS passes (one forward, one reverse), then recurses:

$$ \text{score}(k) = \text{LCS}(A_{\text{left}},, B_{1..k}) + \text{LCS}(A_{\text{right}},, B_{k..}) $$

The maximum over $k \in {0, \ldots, m}$ is found using two $O(m)$-space row computations. The result is provably optimal — Hirschberg never sacrifices correctness, only memory.

Block replacement bailout handles pathological segments (e.g., two 4000-line files where almost every line differs): emit “delete all of $A$, insert all of $B$.” The result is correct but not minimal. Without this guard, Hirschberg would take tens of seconds on adversarial inputs.

2.4 Summary

input
  → strip common prefix/suffix
  → patience anchors (LIS of unique matches)
  → per-segment solver:
       nm ≤ 4M  → exact LCS (full DP)
       nm ≤ 16M → Hirschberg (linear space)
       nm > 16M → block replacement bailout

All three solvers produce optimal (minimum-edit) scripts except the bailout, which is correct but non-minimal. The pipeline is a well-understood combination of textbook algorithms, and there is no theoretical gap — the treewidth-1 guarantee holds throughout.

3. Table Edit Distance

Now we move from treewidth 1 to arbitrary treewidth. Tate’s grid module diffs two 2D tables. First we need a formal definition.

3.1 Definition

Given two tables $T_1 = (R_1, C_1, f_1)$ and $T_2 = (R_2, C_2, f_2)$, where $R_i$ is the row set, $C_i$ is the column set, and $f_i : R_i \times C_i \to \Sigma$ is the cell-value function:

Definition (Table Edit Distance). The table edit distance $\tau(T_1, T_2)$ is the minimum total cost of a sequence of operations transforming $T_1$ into $T_2$:

OperationCostEffect
insert_row$\alpha$Add a row
delete_row$\alpha$Remove a row
insert_col$\beta$Add a column
delete_col$\beta$Remove a column
modify_cell$\gamma$Change a cell value

where $\alpha, \beta, \gamma > 0$.

When both tables have one column, $\tau$ reduces to the 1D edit distance $d(A, B) = n + m - 2L(A,B)$. This confirms it’s a genuine generalization.

3.2 Metric Axioms

Theorem. $\tau$ is a metric for any fixed $\alpha, \beta, \gamma > 0$.

Proof. We verify the four axioms.

(i) Non-negativity: $\tau \geq 0$ since all costs are positive.

(ii) Identity: $\tau(T, T) = 0$ (no operations needed). If $\tau(T_1, T_2) = 0$, zero operations were performed, so $T_1 = T_2$.

(iii) Symmetry: Every operation has an inverse of equal cost: insert_row $\leftrightarrow$ delete_row, insert_col $\leftrightarrow$ delete_col, modify_cell is self-inverse. An optimal script $T_1 \to T_2$ reverses to a script $T_2 \to T_1$ of the same cost.

(iv) Triangle inequality: Let $S_{12}$ be an optimal script $T_1 \to T_2$ and $S_{23}$ an optimal script $T_2 \to T_3$. The concatenation $S_{12} \circ S_{23}$ is a valid script $T_1 \to T_3$ with cost $\tau(T_1, T_2) + \tau(T_2, T_3)$. Since $\tau(T_1, T_3)$ is the minimum:

$$ \tau(T_1, T_3) \leq \tau(T_1, T_2) + \tau(T_2, T_3). \quad \blacksquare $$

4. NP-Hardness

The constraint graph for table edit distance is a grid of treewidth $\min(|R|, |C|)$. When both dimensions are unbounded, treewidth is unbounded, and we should expect NP-hardness. The following theorem confirms this — and shows the hardness holds for any positive cost model.

4.1 Universal Hardness

Theorem. For any $\alpha, \beta, \gamma > 0$, computing $\tau(T_1, T_2)$ is NP-hard.

This is stronger than exhibiting one intractable cost setting. It says: no choice of positive costs makes the problem polynomial.

Proof (reduction from Maximum Biclique). Maximum Biclique asks: given a bipartite graph $G = (U, V, E)$ and integer $k$, does $G$ contain a $K_{k,k}$ complete bipartite subgraph? This problem is NP-complete.

Construction. Given $(G, k)$:

  1. $A$ = $|U| \times |V|$ adjacency matrix of $G$.
  2. $B$ = $k \times k$ all-ones matrix.

Since $B$ has $k$ rows and $k$ columns, any edit script transforming $A$ into $B$ can match at most $k$ rows and $k$ columns. Parameterize a strategy by $(k_A, k_B)$: match $k_A \leq k$ rows, match $k_B \leq k$ columns, delete the rest, insert any shortfall.

The cost decomposes as:

$$ \text{cost}(k_A, k_B) = \alpha(|U| + k - 2k_A) + \beta(|V| + k - 2k_B) + \gamma \cdot \text{mismatches}(k_A, k_B) $$

where $\text{mismatches}(k_A, k_B)$ is the number of cells in the $k_A \times k_B$ matched submatrix where $A$ disagrees with $B$.

Define the threshold:

$$ \theta = \alpha(|U| - k) + \beta(|V| - k) $$

This is the cost when $k_A = k$, $k_B = k$, and mismatches $= 0$ — i.e., we match exactly $k$ rows and $k$ columns with no cell modifications.

Key lemma. For any strategy $(k_A, k_B)$:

$$ \text{cost}(k_A, k_B) - \theta = 2\alpha(k - k_A) + 2\beta(k - k_B) + \gamma \cdot \text{mismatches}(k_A, k_B) \geq 0 $$

All three terms are non-negative. Equality holds if and only if $k_A = k$, $k_B = k$, and $\text{mismatches} = 0$.

YES case (biclique exists): There exist $k$ rows and $k$ columns in $A$ forming an all-ones submatrix. Matching them gives $\text{cost} = \theta$. So $\tau(A, B) = \theta$.

NO case (no biclique): Any $k \times k$ submatrix of $A$ has at least one zero, so $\text{mismatches}(k, k) \geq 1$. For any strategy, at least one of the three non-negative terms in the lemma is strictly positive, so $\text{cost}(k_A, k_B) > \theta$. Therefore $\tau(A, B) > \theta$.

Since $G$ has a $K_{k,k}$ biclique if and only if $\tau(A, B) = \theta$, an oracle for $\tau$ solves Maximum Biclique in polynomial time. $\blacksquare$

4.2 Why the Universal Version Matters

The proof does not assume any relationship between $\alpha$, $\beta$, and $\gamma$. The key insight is that matching fewer rows costs both a deletion and an insertion (each costing $\alpha$), so the penalty for “unmatching” a row is $2\alpha$. This penalty is always positive, regardless of how cell modification costs compare to row/column costs.

In the NO case, every strategy pays at least $2\alpha$, $2\beta$, or $\gamma$ above $\theta$. The separation does not depend on any cost being “large.” The hardness is inherent to the 2D alignment structure — exactly what treewidth predicts.

5. Bounded Treewidth: FPT

When the smaller dimension is bounded, treewidth is bounded, and the exponential factor $d^{aw}$ becomes manageable.

Theorem (FPT). If $|C_1|, |C_2| \leq m$, then $\tau(T_1, T_2)$ can be computed in $O(2^{m_1 + m_2} \cdot n_1 \cdot n_2)$ time.

Proof sketch. Enumerate all $O(2^{m_1 + m_2})$ possible column alignments. For each fixed column alignment, row alignment reduces to a 1D problem: compute row signatures (cells at matched columns, joined into a key) and solve by the standard $O(n_1 n_2)$ LCS DP. Take the minimum over all column alignments. $\blacksquare$

This is the treewidth theorem in action: the grid’s treewidth is $\min(\text{rows}, \text{cols})$, and bounding the column count bounds the treewidth. The exponential cost lives in the treewidth, not the input size.

A more general result subsumes this: Courcelle’s theorem (1990) states that any property definable in monadic second-order logic is decidable in linear time on bounded-treewidth graphs. Table edit distance is expressible in MSO (it quantifies over edit scripts), so Courcelle’s theorem directly guarantees FPT — our explicit enumeration is one concrete instantiation.

What’s Next

Treewidth answers when table edit distance is tractable. But it’s a graph-theoretic symptom, not the root cause. The remaining posts go deeper.

Why does the boundary exist?

Treewidth says 1D is easy and 2D is hard, but doesn’t explain why the DP machinery works in one case and fails in the other. The answer is algebraic: 1D alignments admit polymorphisms — operations that combine two valid alignments into a third — giving the solution space a lattice structure that dynamic programming exploits. 2D alignments lack a Taylor term (the weakest non-triviality condition from universal algebra), so no composition structure exists. This is the same boundary Bulatov and Zhuk identified in their 2017 proof of the CSP dichotomy conjecture, now applied to structured diff.

What about higher dimensions?

A $d$-dimensional tensor’s edit distance requires aligning $d$ coupled axes. The boundary $d = 1$ vs $d \geq 2$ maps precisely onto tensor rank: matrix rank (order 2) is polynomial; tensor rank for order $\geq 3$ is NP-hard (Håstad, 1990). Treewidth of a $d$-dimensional grid is $\min_i n_i$, so fixing $d - 1$ dimensions restores tractability — but the enumeration cost is $O(2^{\sum m_i} \cdot n^2)$. Whether this is tight connects to the W[1]-hardness of $d$-dimensional matching.

How does tate cope with NP-hardness?

When treewidth is unbounded, exact computation is infeasible. tate uses coordinate descent: alternately re-align rows (holding columns fixed) and columns (holding rows fixed). Each step is an exact LCS solve; the cost monotonically decreases and converges to a local optimum in finite steps. We prove convergence and discuss the gap to global optimality — unbounded in the worst case, but small on real-world structured tables.

Can the hardness be used constructively?

Bounded treewidth enables not just FPT algorithms but FPT-sized zero-knowledge proofs — proofs whose size is $f(w) \cdot \text{poly}(n)$ where $w$ is the treewidth, not the circuit size. Applications: privacy-preserving comparison of medical databases, verifiable outsourced table diffing, and federated data quality checks where parties cannot reveal raw data.

The code for all of this is in tate, with full algorithm documentation in ALGORITHMS.md.