Left-maximal DFS-tree complexity in digraphs

Problem 3 · arXiv:2304.03567

arXiv Problem high confidence— first stated 2024-01-11

Authors: Stéphane Bessy, Stéphan Thomassé, Laurent Viennot

Status open high confidence

Problem 3 from arXiv:2304.03567 asks whether a left-maximal DFS-tree can be computed in o(n²) time in minimally strongly connected digraphs, and what the complexity is in the general strongly connected case. The current O(n²) algorithm is identified by the authors as the complexity bottleneck of their balanced bi-tree construction. No follow-up work addressing this algorithmic question was found in a web search covering the period since the paper's appearance at STACS 2024.

Reviewer notes. No follow-up found after four web calls (two searches + two fetches). The problem is a concrete algorithmic open question: improve the O(n²) bottleneck for computing a left-maximal DFS-tree in minimally (or generally) strongly connected digraphs. The paper appeared at STACS 2024; the problem is roughly 2 years old with no resolution found.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. Can we compute a left-maximal dfs-tree in $o(n^{2})$ time in minimally strongly connected digraphs? What about the complexity in the general case?

Context

The Left-DFS tree is a key algorithmic ingredient introduced in the paper for constructing balanced bi-trees. The current construction runs in $O(n^{2})$ time; whether this can be improved is left open, both for the minimally strongly connected special case and for general strongly connected digraphs.

Source paper

Temporalizing digraphs via linear-size balanced bi-trees
Stéphane Bessy, Stéphan Thomassé, Laurent Viennot · 2024-01-11
https://arxiv.org/abs/2304.03567