| Approximate Hypergraph Partitioning and Applications (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract We show that any partition-problem of hypergraphs has a sublinear O(n) time algorithm(where n is the number of vertices) with the following property: Given an input hypergraph H,which satisfies the partition problem, the algorithm produces a partition of H that is "close " tosatisfying it. In case no such partition of H exists, the algorithm rejects the input. We also obtainproperty testing algorithms for such problems making only poly(1 /ffl) queries, and with a constantrunning time. This extends the results of Goldreich, Goldwasser and Ron who obtained similar algorithms for the special case of graph partition problems in their seminal paper [16].We present several applications of our result, and in the foremost a new application related to Szemer'edi's regularity lemma [27]. The applications we describe are the following.* By using an appropriate hypergraph modeling of the problem we design a surprisingly simple O(n) time algorithm for constructing regular partitions of graphs. An added benefit is thatunlike the previous approaches for constructing regular partitions [3, 10, 14, 15, 21], which proved the lemma "algorithmically", our algorithm will find a small regular partition in thecase that one exists in our input graph, rather than being guaranteed to find only a partition of the tower-size upper bound given by Szemer'edi's lemma itself. * For arbitrary r> = 3, we design an O(n) time randomized algorithm for constructing reg-ular partitions of r-uniform hypergraphs. This improves over the previous (deterministic)algorithms [8, 15] that had a running time of O(n2r-1).* Our property testing algorithm provides a common generalization for many previouslyknown results. We show how special cases of the now-testable partition problem can be easily used to derive some results that were previously proved using specialized methods,namely testing properties of hypergraphs [7, 23] and estimating | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||