Finding induced acyclic subgraphs in random digraphs
The electronic journal of combinatorics, Tome 10 (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^{\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.
@article{10_37236_1739,
author = {C. R. Subramanian},
title = {Finding induced acyclic subgraphs in random digraphs},
journal = {The electronic journal of combinatorics},
year = {2003},
volume = {10},
doi = {10.37236/1739},
zbl = {1031.05119},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1739/}
}
C. R. Subramanian. Finding induced acyclic subgraphs in random digraphs. The electronic journal of combinatorics, Tome 10 (2003). doi: 10.37236/1739
Cité par Sources :