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

Kunal Dutta ; C.R. Subramanian

Discussiones Mathematicae Graph Theory, Tome 34 (2014), p. 467-495 / Harvested from The Polish Digital Mathematics Library

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 ∈ 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

Détail

Publié le : 2014-01-01

Zbl 1295.05209

EUDML-ID : urn:eudml:doc:268069

Bibliographie

[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] | Zbl 1094.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] | Zbl 0910.05058

[3] N. Alon and J.H. Spencer, The Probabilistic Method (Wiley International, 2001). | Zbl 1333.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. | Zbl 1283.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). | Zbl 0411.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] | Zbl 0771.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] | Zbl 0849.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] | Zbl 0768.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. | Zbl 1196.05091

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