3 + ε Approximation of Tree Edit Distance in Truly Subquadratic Time
summary
Proves a 3 + ε approximation for tree edit distance running in truly subquadratic time (about n^1.99). Converts rooted trees to strings via parenthesis encoding, builds adaptive windows and super-windows (chosen by milestones and size ranges), computes pairwise distances into a matrix, then runs a higher-dimensional 4D DP that loses a factor 3 from triangle inequality and 1+ε from window rounding. Matches prior edit-distance framework but replaces the reduction so the method actually succeeds for trees. Runtime and approximation are achieved and analyzed.
AI-written summary · about