DMTCS Proceedings, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)

Font Size:  Small  Medium  Large

Induced acyclic subgraphs in random digraphs: Improved bounds

Kunal Dutta, C. R. Subramanian


Given a simple directed graph D = (V,A), let the size of the largest induced directed acyclic graph &em;(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 &masd;. Our main result is that &beqn; &masd;  ≥  ⌊2logq np - X ⌋&nonumber; &eeqn; 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 logq np + Θ(&sqrt;q np).

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional