Kunal Dutta ; C. R. Subramanian
-
Induced acyclic subgraphs in random digraphs: Improved bounds
dmtcs:2795 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2010,
DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
-
https://doi.org/10.46298/dmtcs.2795
Induced acyclic subgraphs in random digraphs: Improved boundsConference paper
Given a simple directed graph D=(V,A), let the size of the largest induced directed acyclic graph (dag) be denoted by mas(D). Let D∈D(n,p) be a random instance, obtained by choosing each of the (n2) 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)≥⌊2logqnp−X⌋ where q=(1−p)−1,X=W if p≥n−1/3+ϵ (ϵ>0 is any constant), X=W/(lnq) if p≥n−1/2(lnn)2, and W is a suitably large constant. where we have an O(lnlnnp/lnq) term instead of W. This improves the previously known lower bound with an O(lnlnnp/lnq) 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 logqnp+Θ(√logqnp).
Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Kunal Dutta;C.R. Subramanian, 2011, On induced acyclic subgraphs in sparse random digraphs, Electronic Notes in Discrete Mathematics, 38, pp. 319-324, 10.1016/j.endm.2011.09.052.