# Induced Acyclic Tournaments in Random Digraphs: Sharp Concentration, Thresholds and Algorithms

Discussiones Mathematicae Graph Theory (2014)

- Volume: 34, Issue: 3, page 467-495
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topKunal Dutta, and C.R. Subramanian. "Induced Acyclic Tournaments in Random Digraphs: Sharp Concentration, Thresholds and Algorithms." Discussiones Mathematicae Graph Theory 34.3 (2014): 467-495. <http://eudml.org/doc/268069>.

@article{KunalDutta2014,

abstract = {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 Ϟ(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(logrn) + 0.5⌋ and r = p−1. It is also shown that if, asymptotically, 2(logrn) + 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(logrn) + 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 logrn + Θ(√logrn). 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},

author = {Kunal Dutta, C.R. Subramanian},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {random digraphs; tournaments; concentration; thresholds; algorithms},

language = {eng},

number = {3},

pages = {467-495},

title = {Induced Acyclic Tournaments in Random Digraphs: Sharp Concentration, Thresholds and Algorithms},

url = {http://eudml.org/doc/268069},

volume = {34},

year = {2014},

}

TY - JOUR

AU - Kunal Dutta

AU - C.R. Subramanian

TI - Induced Acyclic Tournaments in Random Digraphs: Sharp Concentration, Thresholds and Algorithms

JO - Discussiones Mathematicae Graph Theory

PY - 2014

VL - 34

IS - 3

SP - 467

EP - 495

AB - 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 Ϟ(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(logrn) + 0.5⌋ and r = p−1. It is also shown that if, asymptotically, 2(logrn) + 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(logrn) + 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 logrn + Θ(√logrn). 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

LA - eng

KW - random digraphs; tournaments; concentration; thresholds; algorithms

UR - http://eudml.org/doc/268069

ER -

## References

top- [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[Crossref] Zbl1094.05048
- [2] N. Alon and M. Krivelevich, The concentration of the chromatic number of random graphs, Combinatorica 17 (1997) 303-313. doi:10.1007/BF01215914[WoS][Crossref] Zbl0910.05058
- [3] N. Alon and J.H. Spencer, The Probabilistic Method (Wiley International, 2001). Zbl1333.05001
- [4] B. Bollob´as, Random Graphs (2nd Edition, Cambdrige University Press, 2001). doi:10.1017/CBO9780511814068[Crossref]
- [5] B. Bollob´as and P. Erd˝os, Cliques in random graphs, Math. Proc. Cambridge Philos. Soc. 80 (1988) 419-427. doi:10.1017/S0305004100053056[Crossref]
- [6] B.K. Rosen, Robust linear algorithms for cutsets, J. Algorithms 3 (1982) 205-217. doi:10.1016/0196-6774(82)90020-7[Crossref]
- [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. Zbl1283.05248
- [8] K. Dutta and C.R. Subramanian, Induced acyclic subgraphs in random digraphs: Im- proved 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.[Crossref]
- [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[Crossref]
- [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). Zbl0411.68039
- [12] J. Hastad, Clique is hard to approximate within n1−", Acta Math. 182 (1999) 105-142. doi:10.1007/BF02392825[Crossref]
- [13] S. Janson, T. Luczak and A. Ruci´nski, Random Graphs (John Wiley & Sons, Inc., 2000). doi:10.1002/9781118032718[Crossref]
- [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[Crossref]
- [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[WoS][Crossref] Zbl0771.05091
- [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[Crossref]
- [19] R. Motwani and P. Raghavan, Randomized Algorithms (Cambridge University Press, 1995). doi:10.1017/CBO9780511814075[Crossref] Zbl0849.68039
- [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.[Crossref]
- [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[Crossref] Zbl0768.68181
- [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. Zbl1196.05091
- [23] C.R. Subramanian, Finding induced acyclic subgraphs in random digraphs, Electron. J. Combin. 10 (2003) #R46. Zbl1031.05119

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.