Induced acyclic tournaments in random digraphs: Sharp concentration, thresholds and algorithms

Dutta, Kunal  ; Subramanian, C.R.

Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 3, pp. 467-495

Résumé

Given a simple directed graph D = (V,A), let the size of the largest induced acyclic tournament be denoted by mat(D). Let D ∈ 𝒟(n, p) (with p = p(n)) be a random instance, obtained by randomly orienting each edge of a random graph drawn from 𝒢(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_rn) + 0.5⌋ and r = p^−1. It is also shown that if, asymptotically, 2(log_rn) + 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_rn) + 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_rn + Θ(√(log_rn)). 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.

Détail

Keywords: random digraphs, tournaments, concentration, thresholds, algorithms