Finding Induced Acyclic Subgraphs in Random Digraphs

C. R. Subramanian

Abstract


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^{\epsilon})$ for some $\epsilon>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.


Full Text: PDF