An algorithmic version of the blow-up lemma
1998; Wiley; Volume: 12; Issue: 3 Linguagem: Inglês
10.1002/(sici)1098-2418(199805)12
ISSN1098-2418
AutoresJános Komlós, Gábor N. Sárközy, Endre Szemerédi,
Tópico(s)Complexity and Algorithms in Graphs
ResumoRandom Structures & AlgorithmsVolume 12, Issue 3 p. 297-312 An algorithmic version of the blow-up lemma János Komlós, János Komlós [email protected] Mathematics Department, Rutgers University, New Brunswick, NJ 08903Search for more papers by this authorGabor N. Sarkozy, Corresponding Author Gabor N. Sarkozy [email protected] Computer Science Department, Worcester Polytechnic Institute, Worcester, MA 01609 Part of this paper was written while Sarkozy was visiting MSRI Berkeley, as part of the Combinatorics Program. Research at MSRI is supported in part by NSF grant DMS-9022140.Computer Science Department, Worcester Polytechnic Institute, Worcester, MA 01609Search for more papers by this authorEndre Szemerédi, Endre Szemerédi [email protected] Computer Science Department, Rutgers University, New Brunswick, NJ 08903Search for more papers by this author János Komlós, János Komlós [email protected] Mathematics Department, Rutgers University, New Brunswick, NJ 08903Search for more papers by this authorGabor N. Sarkozy, Corresponding Author Gabor N. Sarkozy [email protected] Computer Science Department, Worcester Polytechnic Institute, Worcester, MA 01609 Part of this paper was written while Sarkozy was visiting MSRI Berkeley, as part of the Combinatorics Program. Research at MSRI is supported in part by NSF grant DMS-9022140.Computer Science Department, Worcester Polytechnic Institute, Worcester, MA 01609Search for more papers by this authorEndre Szemerédi, Endre Szemerédi [email protected] Computer Science Department, Rutgers University, New Brunswick, NJ 08903Search for more papers by this author First published: 07 December 1998 https://doi.org/10.1002/(SICI)1098-2418(199805)12:3 3.0.CO;2-QCitations: 45 AboutPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onEmailFacebookTwitterLinkedInRedditWechat Abstract Recently we developed a new method in graph theory based on the regularity lemma. The method is applied to find certain spanning subgraphs in dense graphs. The other main general tool of the method, besides the regularity lemma, is the so-called blow-up lemma (Komlós, Sárközy, and Szemerédi [Combinatorica, 17, 109–123 (1997)]. This lemma helps to find bounded degree spanning subgraphs in ε-regular graphs. Our original proof of the lemma is not algorithmic, it applies probabilistic methods. In this paper we provide an algorithmic version of the blow-up lemma. The desired subgraph, for an n-vertex graph, can be found in time O(nM(n)), where M(n)=O(n2.376) is the time needed to multiply two n by n matrices with 0, 1 entires over the integers. We show that the algorithm can be parallelized and implemented in NC5. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 297–312, 1998 References 1 N. Alon, Non-constructive proofs in combinatorics, Proceedings of the International Congress of Mathematics, Kyoto 1990, Japan, Springer-Verlag, Tokyo, 1991, pp. 1421–1429. Google Scholar 2 N. Alon, A parallel algorithmic version of the local lemma, Random Struct. Algorithms, 2, 367–378 (1991)., 10.1002/rsa.3240020403 Web of Science®Google Scholar Proceedings of the Thirty-Second IEEE FOCS (1991)., pp. 586–593. Google Scholar 3 N. Alon, R. Duke, H. Lefman, V. Rodl, and R. Yuster, The algorithmic aspects of the regularity lemma, Proceedings of the Thirty-Third IEEE FOCS (1993)., pp. 479–481, Google Scholar J. Algorithms, 16, 80–109 (1994). 10.1006/jagm.1994.1005 Web of Science®Google Scholar 4 N. Alon, L. Babai, and A. Itai, A fast randomized parallel algorithm for the maximal independent set problem, J. Algorithms, 7, 567–583 (1986). 10.1016/0196-6774(86)90019-2 Web of Science®Google Scholar 5 N. Alon and R. Yuster, Almost H-factors in dense graphs, Graphs Combin., 8, 95–102 (1992). 10.1007/BF02350627 Web of Science®Google Scholar 6 N. Alon and R. Yuster, H-factors in dense graphs, J. Combin. Theory Ser. B, 66, 269–282 (1996). 10.1006/jctb.1996.0020 Web of Science®Google Scholar 7 J. Beck, An algorithmic approach to the Lovász local lemma, Random Struct. Algorithms, 2, 343–365 (1991). 10.1002/rsa.3240020402 Web of Science®Google Scholar 8 B. Bollobás, P. Erdös, M. Simonovits, and E. Szemerédi, Extremal graphs without large forbidden subgraphs, in Advances in Graph Theory, Cambridge Combinatorial Conference, Trinity College, 1977, Ann. Discrete Math., 3, 29–41 (1978). 10.1016/S0167-5060(08)70495-3 Google Scholar 9 V. Chvátal, V. Rödl, E. Szemerédi, and W. T. Trotter Jr., The Ramsey number of a graph with bounded maximum degree, J. Combin. Theory Ser. B, 34, 239–243 (1983). 10.1016/0095-8956(83)90037-0 Web of Science®Google Scholar 10 S. A. Cook, Taxonomy of problems with fast parallel algorithms, Inform. and Control. 64, 2–22 (1985). 10.1016/S0019-9958(85)80041-3 Web of Science®Google Scholar 11 P. Erdös, P. Frankl, and V. Rödl, The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs Combin., 2, 113–121 (1986). 10.1007/BF01788085 Web of Science®Google Scholar 12 P. Franek and V. Rödl, On Erdös conjecture for multiplicities of complete subgraphs, Graphs Combin., to appear. Google Scholar 13 P. Frankl, R. L. Graham, and V. Rödl, On subsets of Abelian groups with no 3-term arithmetic progression, J. Combin. Theory Ser. A, 15, 157–161 (1987). 10.1016/0097-3165(87)90053-7 Web of Science®Google Scholar 14 P. Frankl and Z. Füredi, Exact solution of some Turán-type problems, J. Combin Theory Ser. A, 45, 226–262 (1987). 10.1016/0097-3165(87)90016-1 Web of Science®Google Scholar 15 Z. Füredi, The maximum number of edges in a minimal graph of diameter 2, J. Graph Theory, 16, 81–98 (1992). 10.1002/jgt.3190160110 Web of Science®Google Scholar 16 Z. Füredi, M. Goemans, and D. J. Kleitman, On the maximum number of triangles in wheel-free graphs, to appear. Google Scholar 17 M. Goldberg and T. Spencer, A new parallel algorithm for the maximal independent set problem, SIAM J. Comput., 18, 419–427 (1989). 10.1137/0218029 Web of Science®Google Scholar 18 M. Goldberg and T. Spencer, Constructing a maximal independent set in parallel, SIAM J. Disc. Math., 2, 322–328 (1989). 10.1137/0402028 Google Scholar 19 A. Hajnal, W. Maass, and G. Turan, On the communication complexity of graph properties, Proceedings of the Twentieth Symposium on Theory of Computing, 1988, pp. 186–191. Google Scholar 20 J. E. Hopcroft and R. M. Karp, An n1/2> algorithm for maximum matchings in bipartite graphs, SIAM J. Comput., 2, 225–231 (1973). 10.1137/0202019 Google Scholar 21 R. Karp and V. Ramachandran, Parallel algorithms for shared memory machines, in Handbook of Theoretical Computer Science, J. Van Leeuven, Ed., North-Holland, Amsterdam, 1990, pp. 869–941. Google Scholar 22 R. Karp and A. Wigderson, A fast parallel algorithm for the maximal independent set problem, J. Assoc. Comput. Mach., 32, 762–773 (1985). 10.1145/4221.4226 Web of Science®Google Scholar 23 J. Komlós, G. N. Sárközy, and E. Szeméredi, Proof of a packing conjecture of Bollobas Combinatorics, Probab. Comput., 4, 241–255 (1995). 10.1017/S0963548300001620 Google Scholar 24 J. Komlós, G. N. Sárközy, and E. Szemerédi, Blow-up lemma, Combinatorica, 17, 109–123 (1997). 10.1007/BF01196135 Web of Science®Google Scholar 25 J. Komlós, G. N. Sárközy, and E. Szemerédi, On the Pósa –Seymour conjecture, J Graph Theory, to appear. Google Scholar 26 J. Komlós, G. N. Sárközy, and E. Szemerédi, On the square of a Hamiltonian cycle in dense graphs, Random Structures and Algorithms, 9, 193–211 (1996). 10.1002/(SICI)1098-2418(199608/09)9:1/2 3.0.CO;2-P Web of Science®Google Scholar 27 J. Komlós, G. N. Sárközy, and E. Szemerédi, Proof of the Seymour conjecture for large graphs, submitted for publication. Google Scholar 28 J. Komlós, G. N. Sárközy, and E. Szeméredi, Proof of the Alon–Yuster conjecture, in preparation. Google Scholar 29 J. Komlós and M. Simonovits, Szemerédi's regularity lemma and its applications in graph theory, in Paul Erdös is 80, Vol. 2., Proc. Colloq. Math. Soc. János Bolyai 295–352 (1996). Google Scholar 30 L. Lovász and M. D. Plummer, Matching theory, Ann. Discrete Math., 29 (1986). Google Scholar 31 M. Luby, A simple parallel algorithm for the maximal independent set problem, SIAM J. Comput., 15, 1036–1053 (1986). 10.1137/0215074 Web of Science®Google Scholar 32 C. H. Papadimitriou, On graph theoretic lemmata and complexity classes, Proceedings of the Thirty-First IEEE FOCS, 1990, pp. 794–801. Google Scholar 33 C. H. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, J. Comput. System Sci., 47 (1993). Google Scholar 34 N. J. Pippenger, On simultaneous resource bounds, Proceedings of the Twentieth IEEE FOCS, 1979, pp. 307–311. Google Scholar 35 V. Rodl, On universality of graphs with uniformly distributed edges, Discrete Math., 59, 125–134 (1986). 10.1016/0012-365X(86)90076-2 Web of Science®Google Scholar 36 G. N. Sárközy, Fast parallel algorithms for finding Hamiltonian cycles and trees in graphs, Technical Report 93-81, DIMACS, Rutgers University, New Brunswick, NJ, 1993. Google Scholar 37 M. Simonovits and V. T. Sös, Szemerédi's partition and quasirandomness, Random Struct. Algorithms, 2, 1–10 (1991). 10.1002/rsa.3240020102 Web of Science®Google Scholar 38 E. Szemerédi, Regular partitions of graphs, in Colloques Internationaux C. N. R. S., J.-C. Bermond, J.-C. Fournier, M. Las Vergnas, and D. Sotteau, Eds., 1978, pp. 399–401. Google Scholar 39 E. Szemerëdi, On a set containing no k elements in arithmetic progression, Acta Arith., XXVII, 199–245 (1975). Google Scholar 40 L. G. Valiant, Parallel computation, Proceedings of the Seventh IBM Symposium on Mathematical Foundations of Computer Science, 1982. Google Scholar Citing Literature Volume12, Issue3May 1998Pages 297-312 ReferencesRelatedInformation
Referência(s)