Finding induced acyclic subgraphs in random digraphs (Q1422133)

Summary: 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^{\varepsilon})\) for some \(\varepsilon > 0\). We study this problem when \(D\) is a random instance. We show that, almost surely, any maximal solution is within an \(o(\ln 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.