Premium
An algorithmic version of the blow‐up lemma
Author(s) -
Komlós János,
Sarkozy Gabor N.,
Szemerédi Endre
Publication year - 1998
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199805)12:3<297::aid-rsa5>3.0.co;2-q
Subject(s) - lemma (botany) , combinatorics , mathematics , bounded function , discrete mathematics , vertex (graph theory) , probabilistic method , graph , probabilistic logic , spanning tree , induced subgraph isomorphism problem , graph theory , line graph , voltage graph , mathematical analysis , ecology , statistics , poaceae , biology
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 ( n M ( n )), where M ( n )= O ( n 2.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 N C 5 . © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 297–312, 1998