Induced acyclic subgraphs in random digraphs: Improved bounds
Kunal Dutta, C. R. Subramanian
Abstract
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