### 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 NC^{1}.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992 |

Publisher | IEEE Computer Society |

Pages | 473-481 |

Number of pages | 9 |

ISBN (Electronic) | 0818629002 |

DOIs | |

State | Published - Jan 1 1992 |

Externally published | Yes |

Event | 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992 - Pittsburgh, United States Duration: Oct 24 1992 → Oct 27 1992 |

### Publication series

Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

Volume | 1992-October |

ISSN (Print) | 0272-5428 |

### Conference

Conference | 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992 |
---|---|

Country | United States |

City | Pittsburgh |

Period | 10/24/92 → 10/27/92 |

### All Science Journal Classification (ASJC) codes

- Computer Science(all)

## Cite this

*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