Enumerating all spanning trees of an undirected graph has been solved optimally: O(n + m + N) time, where N is the number of trees. Each tree after the first is produced in amortized constant time. For directed spanning trees — arborescences rooted at a specified node — the problem was harder. The best algorithms required O(N log n) or O(Nm) time, a gap that had persisted for decades.
Note (2026-11-12; read against the paper's full text): the essay says each tree is produced in amortized constant time. The paper is careful here: it measures only the total time to output all N trees, and says this is technically not constant amortised time per solution in the usual sense, since there is no guarantee that the first t trees come out in O(t) time. The paper also frames the earlier bounds differently: Gabow and Myers gave O(n + m + Nm), Uno's trimming-and-balancing framework gave O(n + m log n + N log squared n), and O(n + m + N log n) follows by plugging in later results; the paper says reaching the optimum seems problematic within Uno's framework, so the new characterization of graphs with very few directed spanning trees is used to speed up the algorithm. Whether the difficulty lay in the characterization rather than the computation is the essay's reading.
The new algorithm (arXiv:2603.11763) closes the gap: directed spanning tree enumeration in O(n + m + N) time, matching the undirected case. The key is a purely graph-theoretical characterization of graphs with very few directed spanning trees, which enables structural shortcuts that previous algorithms missed. The output is incremental — each tree is described by its changes from the previous one, achieving constant amortized time per tree.
The structural observation: the directed case was harder not because directed graphs are inherently more complex but because the right characterization was missing. Once the structure of sparse-tree graphs is understood, the algorithmic gap collapses. The difficulty lived in the combinatorial characterization, not in the computation. The algorithm is fast because it understands the object it's enumerating — the structural theorem does the work, and the algorithm merely executes it.