Induced acyclic subgraphs in random digraphs: Improved bounds

Abstract : Given a simple directed graph $D = (V,A)$, let the size of the largest induced directed acyclic graph $\textit{(dag)}$ be denoted by $mas(D)$. Let $D \in \mathcal{D}(n,p)$ be a $\textit{random}$ instance, obtained by choosing each of the $\binom{n}{2}$ possible undirected edges independently with probability $2p$ and then orienting each chosen edge independently in one of two possible directions with probabibility $1/2$. We obtain improved bounds on the range of concentration, upper and lower bounds of $mas(D)$. Our main result is that $mas(D) \geq \lfloor 2\log_q np - X \rfloor$ where $q = (1-p)^{-1}, X=W$ if $p \geq n^{-1/3+\epsilon}$ ($\epsilon > 0$ is any constant), $X=W/(\ln q)$ if $p \geq n^{-1/2}(\ln n)^2$, and $W$ is a suitably large constant. where we have an $O(\ln \ln np/\ln q)$ term instead of $W$. This improves the previously known lower bound with an $O(\ln \ln np/\ln q)$ term instead of $W$. We also obtain a slight improvement on the upper bound, using an upper bound on the number of acyclic orientations of an undirected graph. We also analyze a polynomial-time heuristic to find a large induced dag and show that it produces a solution whose size is at least $\log _q np + \Theta (\sqrt{\log_q np})$.
Keywords :
Type de document :
Communication dans un congrès
Drmota, Michael and Gittenberger, Bernhard. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), pp.159-174, 2010, DMTCS Proceedings
Domaine :

Littérature citée [17 références]

https://hal.inria.fr/hal-01185594
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 20 août 2015 - 16:33:41
Dernière modification le : mardi 7 mars 2017 - 15:08:06
Document(s) archivé(s) le : mercredi 26 avril 2017 - 09:55:01

Fichier

dmAM0112.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

• HAL Id : hal-01185594, version 1

Citation

Kunal Dutta, C. R. Subramanian. Induced acyclic subgraphs in random digraphs: Improved bounds. Drmota, Michael and Gittenberger, Bernhard. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), pp.159-174, 2010, DMTCS Proceedings. 〈hal-01185594〉

Métriques

Consultations de la notice

70

Téléchargements de fichiers