Optimal FCPP approximation ratio in digraphs
Problem 1 · arXiv:2304.03567
Status open high confidence
Problem 1 asks for the exact value of $r_t$, the best constant-factor approximation ratio achievable for FCPP in strongly connected digraphs. The source paper (STACS 2024) establishes $r_t > 0$ as its central result via a linear-size balanced bi-tree construction of size at least $n/3$, yielding a lower bound on $r_t$; the exact value remains open. No follow-up work resolving or improving upon this bound was found in a thorough web search as of May 2026.
Reviewer notes. Three web searches and fetches of the source paper HTML and arXiv abstract page found no follow-up resolving the exact value of r_t. The paper appeared at STACS 2024 (LIPIcs vol. 289, article 13). The supplied internal references (arXiv:2206.12335, listed twice) are confirmed unrelated via WebFetch — they are a percolation paper by Balister, Johnston, Savery, and Scott, a clear fuzzy-match false positive.
Context
The quantity $r_{t}$ denotes the best approximation ratio achievable for FCPP (Forward Connected Pairs Problem) in strongly connected digraphs. The paper establishes $r_{t}>0$ as its central result, but the exact value of $r_{t}$ remains open. The paper shows $r_{t}\geq 1/9$ via its bi-tree construction.
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