Exact feedback sets in cyclic tournament substitutions

Definitions and mathematical statement

Let $D=(V,E)$ be a finite simple digraph with no directed cycle of length at most three. Thus loops, opposite arcs, and cyclically oriented triangles are all absent. An unordered pair of distinct vertices $\{u,v\}$ is a nonedge if neither $u\to v$ nor $v\to u$ belongs to $E$. Let \[ k=\left|\left\{\{u,v\}\in\binom V2: u\to v,v\to u\notin E\right\}\right|. \] A feedback arc set is a subset $F\subseteq E$ such that deleting its arcs leaves no directed cycle of any length. Write $\tau(D)=\min\{|F|:F\text{ is a feedback arc set}\}$.

The Chudnovsky--Seymour--Sullivan conjecture asks whether \[ \tau(D)\le\lfloor k/2\rfloor \] for every such digraph. Missing pairs are counted once, while deleted arcs are individual directed edges. Vertices are retained throughout. Equivalently, there should be a linear ordering of $V$ with at most $\lfloor k/2\rfloor$ arcs pointing backwards: deleting these arcs leaves an acyclic graph, and every finite acyclic digraph admits an ordering in which all arcs point forwards. The hypothesis only forbids short directed cycles, while the conclusion removes all directed cycles. A transitive triangle is permitted, and the original graph need not have any particular ordering, connectedness, or degree conditions.

Short English statement

Can every digraph without a directed triangle or digon be made acyclic by deleting at most half as many arcs as it has missing unordered pairs?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20001072 (AIM-COMBINATORICS-0197), AIM Workshop Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 American Institute of Mathematics, The Caccetta-Haggkvist conjecture, item 6. Original workshop question underlying AIM-COMBINATORICS-0197. https://aimath.org/WWN/caccetta/caccetta.pdf.