Directed tree-width linear constant in regular digraphs
Informal Question on optimal directed tree-width constant for regular digraphs · arXiv:2604.13700
Status open high confidence
The paper (arXiv:2604.13700) establishes that every r-regular digraph has directed tree-width Omega(r), resolving the existence of such a linear lower bound, and proves a specific constant of at least 3/22 via the connection to openly disjoint cycles. The optimal constant epsilon in the lower bound dtw >= epsilon*r remains unknown. The paper was posted 18 days before this review, and no follow-up addressing the optimal constant has been found.
Reviewer notes. No follow-up found; the paper is fewer than 3 weeks old. The paper proves dtw >= (3/22)r as the current best lower bound on epsilon, leaving a gap to the true optimal constant. Steiner's own research page lists this paper as 'submitted' with no citing work yet.
Context
Motivated by Theorem 7 of the paper, which establishes that every $r$-regular digraph has directed tree-width growing with $r$, the authors pose this question about the optimal linear constant in such a lower bound.
Notes. Posed in the text as 'it would be interesting to determine' following Problem 2, without a formal labelled environment.
Source paper
Openly disjoint cycles and directed tree-width of regular digraphs
Raphael Steiner · 2026-04-26
https://arxiv.org/abs/2604.13700