\magnification=1200
\hsize=4in
\overfullrule=0pt
\nopagenumbers
\noindent
%
%
{\bf C.R. Subramanian }
%
%
\medskip
\noindent
%
%
{\bf Finding Induced Acyclic Subgraphs in Random Digraphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
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.

\bye

.