The large-r feedback arc set conjecture for r-free digraphs

Let G=(V,E)G=(V,E) be a digraph on nn vertices, let β(G)\beta(G) denote the minimum size of a feedback arc set, and let an (r1)(r-1)-free digraph be one containing no directed cycle of length at most r1r-1. Large-r feedback arc set conjecture. If GG is an (r1)(r-1)-free digraph and r>2n/3r>2n/3, then

β(G)1.\beta(G)\leq 1.

The claim is presented as a more precise conjecture for the regime where rr is large relative to the number of vertices; no resolution is given.

Sources & referencesView supporting material

Primary source

Jacob Fox, Zoe Himwich and Nitya Mani, “Extremal results on feedback arc sets in digraphs”, arXiv:2204.01938 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.