Engineering Algorithms for Partitioning Large Graphs

• Applicants: Professor Dr. Peter Sanders; Professor Dr. Christian Schulz; Professorin Dr. Dorothea Wagner
• Subject Area: Theoretical Computer Science ; Data Management, Data-Intensive Systems, Computer Science Methods in Business Informatics ; Software Engineering and Programming Languages
• Term: from 2010 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 183646693

Graph partitioning is very important for processing large graphs, e.g. networks stemming from finite element methods, route planning, social networks or web graphs. Often the node set of such graphs needs to be partitioned (or clustered) such that there are few edges between the blocks. In particular, when you process a graph in parallel on k processing elements, you often want to partition the graph into k blocks of about equal size so that there is as little interaction as possible between the blocks. During the first funding period our project was very successful. Our primary goal was to unleash the full potential of the multilevel approach for graph partitioning and related problems. In particular we aimed at a better understanding and an improvement of every component, i.e., contraction including edge ratings and matching, initial partitioning and refinement. On top of that we developed new techniques around multilevel approach, e.g., metaheuristics. One practical outcome was software that is world leading in some important aspects. More precisely, this encompasses highest quality partitions for almost all instances from the Walshaw benchmark set. En passant, we arrived at more powerful algorithms for graph clustering and partitioning and provided the most successful implementations as easy-to-use open source software. In the next project period, our primary goal is to extend our success from the previous project period to more general problems and their applications. Balanced graph partitioning for total cut minimization is only the tip of the iceberg of many related problems that have been less intensively studied but overall have at least an equally wide range of applications. While we expect many of our approaches from the basic problem to help with the more general ones, many new questions and difficulties arise. For example, if we want to partition hypergraphs, the basic approaches may transfer but we get at least two different objective functions and without further ideas, performance will drop dramatically. Further possible generalizations are allowing multiple objectives, and looking at dynamic situations where the graph changes over time. On the other hand, it is also important to look at specializations to families of graphs with particular properties that allow us to compute better solutions more efficiently. Lastly, we will push the envelope with respect to parallelization ranging from shared memory algorithms that better exploit the available hardware to the largest supercomputers where we also need to copartition the input graph and the interconnection network. As in the previous funding period, we will provide the most successful implementations as open source software.

• DFG Programme: Research Grants