2024/09/24 by Diamond, Harvey, Kon, Mark, Raphael, Louise
#05C80 (Primary) 05C85 #68W40 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2409.16443
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 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(Y^* ≤ M ( (1)/(2) -√\fraclog nΔav)) approaches zero exponentially in n, with Y^* the (random) size of the minimum feedback arc set and Δ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 Y^*av ≈ M( (1)/(2) -(1)/(2)√\fraclog nΔav) lies remarkably close graphically to the algorithmically computed average size Y^*av of minimum feedback arc sets.