O(log n) forward cover for strong digraphs

Conjecture 1 · arXiv:2304.03567

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

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

Status open high confidence

The conjecture that every strong digraph on $n$ vertices has an $O(\log n)$ size forward cover remains open. The source paper (STACS 2024) verifies it for bi-oriented graphs via a centroid-decomposition argument and shows a lower bound (Proposition 4) suggesting the logarithmic bound is tight. No subsequent paper resolving the general case was found in the indexed literature.

Reviewer notes. No follow-up paper proving or disproving the O(log n) forward cover conjecture was found after 5 web calls. The conjecture is recent (STACS 2024) and likely still open. The paper also proves existence of linear-size balanced bi-trees (the main technical contribution), which is a separate resolved question. The interval nest digraphs paper arXiv:2603.08585 appeared in search results but its abstract did not mention this conjecture.

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

Conjecture. Every strong digraph $D$ on $n$ vertices has a $O(\log n)$ size forward cover.

Context

A forward cover is a small set of vertex orderings such that every pair of vertices is forward connected in at least one ordering. The conjecture is verified for bi-oriented graphs (undirected graphs with each edge replaced by two arcs) using a centroid-decomposition argument. The general case for arbitrary strongly connected digraphs remains open.

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