zbMATH — the first resource for mathematics

Beyond good shapes: diffusion-based graph partitioning is relaxed cut optimization. (English) Zbl 1310.68167
Cheong, Otfried (ed.) et al., Algorithms and computation. 21st international symposium, ISAAC 2010, Jeju, Korea, December 15–17, 2010. Proceedings, Part II. Berlin: Springer (ISBN 978-3-642-17513-8/pbk). Lecture Notes in Computer Science 6507, 387-398 (2010).
Summary: In this paper we study the prevalent problem of graph partitioning by analyzing the diffusion-based partitioning heuristic Bubble-FOS/C, a key component of the practically successful partitioner DibaP [H. Meyerhenke et al., “A new diffusion-based multilevel algorithm for computing graph partitions”, J. Parallel Distrib. Comput. 69, No. 9, 750–761 (2009)]. Our analysis reveals that Bubble-FOS/C, which yields well-shaped partitions in experiments, computes a relaxed solution to an edge cut minimizing binary quadratic program (BQP). It therefore provides the first substantial theoretical insights (beyond intuition) why Bubble-FOS/C (and therefore indirectly DibaP) yields good experimental results. Moreover, we show that in bisections computed by Bubble-FOS/C, at least one of the two parts is connected. Using arguments based on random walk techniques, we prove that in vertex-transitive graphs actually both parts must be connected components each. All these results may help to eventually bridge the gap between practical and theoretical graph partitioning.
For the entire collection see [Zbl 1202.68003].

68R10 Graph theory (including graph drawing) in computer science
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
DibaP; FOS/C; PT-Scotch
Full Text: DOI