Finding Induced Acyclic Subgraphs in Random Digraphs - Subramanian, C. R. (The Electronic Journal of Combinatorics, 2003)
Consider the problem of finding a large induced acyclic subgraph of a given simple digraph D=(V,E). The decision version of this problem is NP-complete and its optimization is not likely to be approximable within a ratio of O(n^ε) for some ε>0. We study this problem when D is a random instance. We show that, almost surely, any maximal solution is within an o(n) factor from the optimal one. In addition, except when D is very sparse (having n^1+o(1) edges), this ratio is in fact O(1). Thus, the optimal solution can be approximated in a much better way over random instances.