Processing math: 23%

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


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 259 times.
This article's PDF has been downloaded 252 times.