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).

# 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 :
Document type :
Conference papers
Domain :

Cited literature [17 references]

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

### 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⟩

Record views