Extremal results on feedback arc sets in digraphs

For an oriented graph $G$, let $\beta (G)$ denote the size of a minimum feedback arc set, a smallest edge subset whose deletion leaves an acyclic subgraph. Berger and Shor proved that any $m$-edge oriented graph $G$ satisfies $\beta (G)=m/2-\mathrm{\Omega }(m^{3/4})$. We observe that if an oriented graph $G$ has a fixed forbidden subgraph $B$, the bound $\beta (G)=m/2-\mathrm{\Omega }(m^{3/4})$ is sharp as a function of $m$ if $B$ is not bipartite, but the exponent $3/4$ in the lower order term can be improved if $B$ is bipartite. Using a result of Bukh and Conlon on Turán numbers, we prove that any rational number in $[3/4,1]$ is optimal as an exponent for some finite family of forbidden subgraphs. Our upper bounds come equipped with randomized linear-time algorithms that construct feedback arc sets achieving those bounds. We also characterize directed quasirandomness via minimum feedback arc sets.