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

Authors: Kunal Dutta ORCID1; C. R. Subramanian 1

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 DD(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)2logqnpX where q=(1p)1,X=W if pn1/3+ϵ (ϵ>0 is any constant), X=W/(lnq) if pn1/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)
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: Random Graphs,Directed Graphs,Concentration,Largest induced acyclic subgraph,Martingales,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]

1 Document citing this article

Consultation statistics

This page has been seen 257 times.
This article's PDF has been downloaded 251 times.