Search

Given a directed graph, the Minimal Feedback Arc Set (FAS) problem asks for a minimal set of arcs in a directed graph, which, when removed, results in an acyclic graph. Equivalently, the FAS problem asks to find an ordering of the vertices that minimizes the number of feedback arcs. This is considered an algorithmic problem of central importance in discrete mathematics, with varied applications to problems in computer science and operations research. Berger and Shor, in 1990, developed 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 graphs given by the Erd\H{o}s-R\'{e}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. Our interest is in developing a $\textit{lower}$ bound for the minimal feedback arc set that holds with probability 1 as $n\rightarrow \infty$. We show that $$Pr\left(\textbf{Y}^* \le M \left( \frac{1}{2} -\sqrt{\frac{\log n}{2\Delta_{av}}}\right)\right)$$ approaches zero exponentially in $n$, with $\textbf{Y}^*$ the (random) size of the minimal feedback set and $\Delta_{av}=M/n$ the average vertex degree. We subsequently apply our lower bounds to a set of experimental FAS data on related random graphs, as developed by Kathrin Hanauer. Not only does our formula provide a reasonably close lower bound for the minimal set, but the approximation that lies midway between our lower bound and the obvious upper bound of $M/2$ is remarkably close to the computed FAS data over a range of experiments, suggesting that this approximation may in fact be asymptotic to the minimal number of feedback arcs, for large $n$, and an excellent estimate even for moderate values., Comment: 11 pages, 4 figures

Given a directed graph, the Minimal Feedback Arc Set (FAS) problem asks for a minimal set of arcs which, when removed, results in an acyclic graph. Equivalently, the FAS problem asks to find an ordering of the vertices that minimizes the number of feedback arcs. The FAS problem is considered an algorithmic problem of central importance in discrete mathematics. Our purpose in this paper is to consider the problem in the context of Erd\H{o}s-R\'{e}nyi random directed graphs, denoted $D(n,p)$, in which each possible directed arc is included with a fixed probability $p>0$. Our interest is the typical ratio of the number of feedforward arcs to the number of feedback arcs that are removed in the FAS problem. We show that as the number $n$ of vertices goes to infinity the probability that this ratio is greater than $1+\epsilon$ for any fixed $\epsilon > 0$ approaches zero. Similarly, letting $p$ go to zero as $n\rightarrow \infty$ this result remains true if $p>C\log{n}/n$ where $C$ depends on $\epsilon$.