Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

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})$.
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-01185594
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, August 20, 2015 - 4:33:41 PM
Last modification on : Monday, August 19, 2019 - 4:22:06 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 9:55:01 AM

File

dmAM0112.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Kunal Dutta, C. R. Subramanian. Induced acyclic subgraphs in random digraphs: Improved bounds. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. pp.159-174, ⟨10.46298/dmtcs.2795⟩. ⟨hal-01185594⟩

Share

Metrics

Record views

67

Files downloads

403