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

• Autorzy: Kunal Dutta , C.R. Subramanian
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

random digraphs; tournaments; concentration; thresholds; algorithms

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2014
• Tom: 34
• Numer: 3
• Strony: 467-495

Daty

wydano

2014-08-01

otrzymano

2011-04-25

poprawiono

2013-04-29

zaakceptowano

2013-04-29

online

2014-07-16

Twórcy

autor

Kunal Dutta

• The Institute of Mathematical Sciences Taramani, Chennai–600113, India

autor

C.R. Subramanian

• The Institute of Mathematical Sciences Taramani, Chennai–600113, India

Bibliografia

• [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]
• [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]
• [3] N. Alon and J.H. Spencer, The Probabilistic Method (Wiley International, 2001).
• [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.
• [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).
• [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]
• [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]
• [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]
• [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.

Identyfikatory

DOI

10.7151/dmgt.1758