Geodesic
Induced acyclic tournaments in random digraphs: Sharp concentration, thresholds and algorithms
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 3, pp. 467-495.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: random digraphs, tournaments, concentration, thresholds, algorithms 
@article{DMGT_2014_34_3_a1,
     author = {Dutta, Kunal and Subramanian, C.R.},
     title = {Induced acyclic tournaments in random digraphs: {Sharp} concentration, thresholds and algorithms},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {467--495},
     publisher = {mathdoc},
     volume = {34},
     number = {3},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a1/}
}
TY  - JOUR
AU  - Dutta, Kunal
AU  - Subramanian, C.R.
TI  - Induced acyclic tournaments in random digraphs: Sharp concentration, thresholds and algorithms
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2014
SP  - 467
EP  - 495
VL  - 34
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a1/
LA  - en
ID  - DMGT_2014_34_3_a1
ER  - 
%0 Journal Article
%A Dutta, Kunal
%A Subramanian, C.R.
%T Induced acyclic tournaments in random digraphs: Sharp concentration, thresholds and algorithms
%J Discussiones Mathematicae. Graph Theory
%D 2014
%P 467-495
%V 34
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a1/
%G en
%F DMGT_2014_34_3_a1
Dutta, Kunal; Subramanian, C.R. Induced acyclic tournaments in random digraphs: Sharp concentration, thresholds and algorithms. Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 3, pp. 467-495. http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a1/

[1] D. Achlioptas and A. Naor, The two possible values of the chromatic number of a random graph, Ann. of Math. 162 (2005) 1333-1349. doi:10.4007/annals.2005.162.1335

[2] N. Alon and M. Krivelevich, The concentration of the chromatic number of random graphs, Combinatorica 17 (1997) 303-313. doi:10.1007/BF01215914

[3] N. Alon and J.H. Spencer, The Probabilistic Method (Wiley International, 2001).

[4] B. Bollobás, Random Graphs (2nd Edition, Cambdrige University Press, 2001). doi:10.1017/CBO9780511814068

[5] B. Bollobás and P. Erd˝os, Cliques in random graphs, Math. Proc. Cambridge Philos. Soc. 80 (1988) 419-427. doi:10.1017/S0305004100053056

[6] B.K. Rosen, Robust linear algorithms for cutsets, J. Algorithms 3 (1982) 205-217. doi:10.1016/0196-6774(82)90020-7

[7] K. Dutta and C.R. Subramanian, Largest induced acyclic tournament in random digraphs: A 2-point concentration, in: Proceedings of LATIN-2010 (9th Latin American Theoretical Informatics Symposium), Oaxaca, Mexico, April 2010.

[8] K. Dutta and C.R. Subramanian, Induced acyclic subgraphs in random digraphs: Improved bounds, in: Proceedings of AofA-2010 (21st Internatioanl Meeting on Probabilistic and Asymptotic Methods for the Analysis of Algorithms), Vienna, Austria, June 2010, to appear.

[9] R.W. Floyd Assigning meaning to programs, Proc. Sympos. Appl. Math. 19 (1967) 19-32.

[10] A.M. Frieze, On the independence number of random graphs, Discrete Math. 81 (1990) 171-176. doi:10.1016/0012-365X(90)90149-C

[11] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide To The Theory of NP-Completeness (W.H.Freeman, San Francisco, 1978).

[12] J. Hastad, Clique is hard to approximate within n1−", Acta Math. 182 (1999) 105-142. doi:10.1007/BF02392825

[13] S. Janson, T. Luczak and A. Ruciński, Random Graphs (John Wiley & Sons, Inc., 2000). doi:10.1002/9781118032718

[14] S. Khot, Improved inapproximability results for maxclique, chromatic number and approximate graph coloring, in: Proceedings of the 42nd IEEE Symp. Foundations of Computer Science (FOCS 2001) 600-609.

[15] M. Krivelevich and B. Sudakov, Coloring random graph, Inform. Process. Lett. 67 (1998) 71-74. doi:10.1016/S0020-0190(98)00092-1

[16] T. Luczak, A note on the sharp concentration of the chromatic number of random graphs, Combinatorica 11 (1991) 295-297. doi:10.1007/BF01205080

[17] C. Lund and M. Yannakakis, The approximation of maximum subgraph problems, Proceedings of the 20th International Colloquium on Automata, Languages and Programming (ICALP’93), Lecture Notes in Comput. Sci. 700 (1993) 40-51.

[18] M. Cai, X. Deng and W. Zang, An approximation algorithm for feedback vertex set in tournaments SIAM J. Comput. 30 (2001) 1993-2007. doi:10.1137/S0097539798338163

[19] R. Motwani and P. Raghavan, Randomized Algorithms (Cambridge University Press, 1995). doi:10.1017/CBO9780511814075

[20] C.H. Papadimitriou and M. Yannakakis Optimization, approximation, and complex- ity classes, J. Comput. System Sci. (Special issue for the 20th ACM Symposium on Theory of Computing) 43 (1991) 425-440.

[21] E. Speckenmeyer, On feedback problems in digraphs, Proceedings of the 15th International Workshop on Graph Theoretic Concepts in Computer Science (WG’89), Springer-Verlag, Lecture Notes in Comput. Sci. 411 (1990) 218-231. doi:10.1007/3-540-52292-1 16

[22] J.H. Spencer and C.R. Subramanian, On the size of induced acyclic subgraphs in random digraphs, Discrete Math. Theor. Comput. Sci. 10 (2008) 47-54.

[23] C.R. Subramanian, Finding induced acyclic subgraphs in random digraphs, Electron. J. Combin. 10 (2003) #R46.