Constant-factor approximation for RFCPP
Problem 4 · arXiv:2304.03567
Status open high confidence
Problem 4 asks whether a polytime constant approximation algorithm exists for RFCPP (Request Forward Connected Pairs Problem), where only a specified set R of vertex pairs in a strongly connected digraph must be made forward-connected by an enumeration. The source paper (arXiv:2304.03567, STACS 2024) shows FCPP is in APX and proves (Proposition 4) that no constant c>0 can guarantee c|R| satisfied requests for worst-case instances in the undirected sense, but the question of a constant approximation ratio for directed RFCPP is posed explicitly as open. No follow-up paper resolving or substantially progressing Problem 4 was found in the indexed literature as of May 2026.
Reviewer notes. The two internal references are identical false positives (arXiv:2206.12335, about 1-independent percolation), with no connection to the source paper or RFCPP. A topically related paper arXiv:2604.27227 ('Designing sparse temporal graphs satisfying connectivity requirements') appeared in search results but its abstract does not cite arXiv:2304.03567 and no progress on Problem 4 was found in it. No post-2024 resolution of Problem 4 was identified across all web queries.
Context
RFCPP (Request Forward Connected Pairs Problem) is the variant of FCPP where only a specified set $R\subseteq\binom{V}{2}$ of pairs needs to be forward connected. Since FCPP (the case $R=\binom{V}{2}$) is in APX, the question is whether a constant-factor approximation also exists for RFCPP, and in particular whether a linear fraction of requests in $R$ can always be satisfied.
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