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

Kunal Dutta; C.R. Subramanian

Discussiones Mathematicae Graph Theory (2014)

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

Abstract

top
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

How to cite

top

Kunal 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. [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. [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. [3] N. Alon and J.H. Spencer, The Probabilistic Method (Wiley International, 2001). Zbl1333.05001
  4. [4] B. Bollob´as, Random Graphs (2nd Edition, Cambdrige University Press, 2001). doi:10.1017/CBO9780511814068[Crossref] 
  5. [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. [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. [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. [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. [9] R.W. Floyd Assigning meaning to programs, Proc. Sympos. Appl. Math. 19 (1967) 19-32.[Crossref] 
  10. [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. [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. [12] J. Hastad, Clique is hard to approximate within n1−", Acta Math. 182 (1999) 105-142. doi:10.1007/BF02392825[Crossref] 
  13. [13] S. Janson, T. Luczak and A. Ruci´nski, Random Graphs (John Wiley & Sons, Inc., 2000). doi:10.1002/9781118032718[Crossref] 
  14. [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. [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. [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. [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. [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. [19] R. Motwani and P. Raghavan, Randomized Algorithms (Cambridge University Press, 1995). doi:10.1017/CBO9780511814075[Crossref] Zbl0849.68039
  20. [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. [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. [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. [23] C.R. Subramanian, Finding induced acyclic subgraphs in random digraphs, Electron. J. Combin. 10 (2003) #R46. Zbl1031.05119

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.