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- O(m3/ 4). We observe that if an oriented graph G has a fixed forbidden subgraph B, the bound beta(G) = m/2 O(m3/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 Turan 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.