Induced acyclic tournaments in random digraphs: Sharp concentration, thresholds and algorithms
Kunal Dutta, Charumathi Raghu Subramanian · Discussiones Mathematicae Graph Theory · 2014
Given a simple directed graph D = (V, A), let the size of the largest induced acyclic tournament be denoted by mat(D).Let D ∈ D(n, p) (with p = p(n)) be a random instance, obtained by randomly orienting each edge of a random graph drawn from G(n, 2p).We show that mat(D) is asymptotically almost surely (a.a.s.) one of only 2 possible values, namely either b * or b * + 1, where b * = ⌊2(log r n) + 0.5⌋ and r = p -1 .It is also shown that if, asymptotically, 2(log r n) + 1 is not within a distance of w(n)/(ln n) (for any sufficiently slow w(n) → ∞) from an integer, then mat(D) is ⌊2(log r n) + 1⌋ a.a.s.As a consequence, it is shown that mat(D) is 1-point concentrated for all n belonging to a subset of positive integers of density 1 if p is independent of n.It is also shown that there are functions p = p(n) for which mat(D) is provably not concentrated in a single value.We also establish thresholds (on p) for the existence of induced acyclic tournaments of size i which are sharp for i = i(n) → ∞.We also analyze a polynomial time heuristic and show that it produces a solution whose size is at least log r n + Θ( log r n).Our results are valid as long as p ≥ 1/n.All of these results also carry over (with some slight changes) to a related model which allows 2-cycles.