Finding induced acyclic subgraphs in random digraphs
The electronic journal of combinatorics, Tome 10 (2003)
Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website
Zbl EuDML
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.
C. R. Subramanian. Finding induced acyclic subgraphs in random digraphs. The electronic journal of combinatorics, Tome 10 (2003). doi: 10.37236/1739
@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/}
}
Cité par Sources :