Asymptotic Lower Bounds for the Feedback Arc Set Problem in Random Graphs

Abstract

Given a directed graph, the Minimum Feedback Arc Set (FAS) problem asks for a minimum (size) set of arcs in a directed graph, which, when removed, results in an acyclic graph. In a seminal paper, Berger and Shor [1], in 1990, developed initial upper bounds for the FAS problem in general directed graphs. Here we find asymptotic \textit{lower bounds} for the FAS problem in a class of random, oriented, directed graphs derived from the Erdős-Rényi model $G(n,M)$, with n vertices and M (undirected) edges, the latter randomly chosen. Each edge is then randomly given a direction to form our directed graph. We show that $$Pr\left({\text{Y}}^{\ast }\le M\left(\frac{1}{2}-\sqrt{\frac{\log n}{{\Delta }_{av}}}\right)\right)$$ approaches zero exponentially in $n$, with ${\text{Y}}^{\ast }$ the (random) size of the minimum feedback arc set and ${\Delta }_{av}=2M/n$ the average vertex degree. Lower bounds for random tournaments, a special case, were obtained by Spencer [12] and de la Vega [13] and these are discussed. In comparing the bound above to averaged experimental FAS data on related random graphs developed by K. Hanauer [7] we find that the approximation ${\text{Y}}_{av}^{\ast }\approx M\left(\frac{1}{2}-\frac{1}{2}\sqrt{\frac{\log n}{{\Delta }_{av}}}\right)$ lies remarkably close graphically to the algorithmically computed average size ${\text{Y}}_{av}^{\ast }$ of minimum feedback arc sets.

11 pages, 4 figures