The algorithmic aspects of the regularity lemma

N. Alon, R. A. Duke, H. Lefmann, V. Rödl, R. Yuster

Research output: Chapter in Book/Report/Conference proceedingConference contribution

28 Scopus citations

Abstract

The regularity lemma of Szemeredi (1978) is a result that asserts that every graph can be partitioned in a certain regular way. This result has numerous applications, but its known proof is not algorithmic. The authors first demonstrate the computational difficulty of finding a regular partition; they show that deciding if a given partition of an input graph satisfies the properties guaranteed by the lemma is co-NP-complete. However, they also prove that despite this difficulty the lemma can be made constructive; they show how to obtain, for any input graph, a partition with the properties guaranteed by the lemma, efficiently. The desired partition, for an n-vertex graph, can be found in time O(M(n)), where M(n)=O(n/sup 2.376/) is the time needed to multiply two n by n matrices with 0,1-entries over the integers. The algorithm can be parallelized and implemented in NC1.

Original languageEnglish (US)
Title of host publicationProceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992
PublisherIEEE Computer Society
Pages473-481
Number of pages9
ISBN (Electronic)0818629002
DOIs
StatePublished - Jan 1 1992
Externally publishedYes
Event33rd Annual Symposium on Foundations of Computer Science, FOCS 1992 - Pittsburgh, United States
Duration: Oct 24 1992Oct 27 1992

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume1992-October
ISSN (Print)0272-5428

Conference

Conference33rd Annual Symposium on Foundations of Computer Science, FOCS 1992
CountryUnited States
CityPittsburgh
Period10/24/9210/27/92

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Cite this

Alon, N., Duke, R. A., Lefmann, H., Rödl, V., & Yuster, R. (1992). The algorithmic aspects of the regularity lemma. In Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992 (pp. 473-481). [267804] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 1992-October). IEEE Computer Society. https://doi.org/10.1109/SFCS.1992.267804