We touch three different areas: graph partitioning, graph drawing and kernelization techniques for the independent set problem in practice. In particular, we present parallel partitioning algorithms that are able to process huge complex networks which have recently attracted considerable interest. We engineer parallel size-constraint graph clustering algorithms that are used as a subroutine at multiple stages of multilevel graph partitioning. The resulting system is more scalable and achieves higher quality than other state-of-the-art systems. As an example, we partition a web graph with 3.3G edges in 16 seconds on a high-performance cluster and compute a high quality partition -- none of the competing systems can handle this graph. In another line of research, we compute graph layouts using a multilevel algorithm with respect to a recently proposed metric that combines layout stress and entropy. Drawing large graphs appropriately is an important step for the visual analysis of data from real-world networks. The proposed system uses a simple local iterative scheme within a multilevel approach, approximates long-range forces and uses shared-memory parallelism. In comparison to the previously best maxent-stress optimizer, which is sequential, our parallel implementation is on average 30 times faster while producing comparable solution quality. Lastly, we develop an advanced evolutionary algorithm, which incorporates kernelization techniques to compute large independent sets in huge sparse networks. The key idea is to apply an evolutionary algorithm on a problem kernel, and then proceed recursively with inexact kernelization techniques. This opens up the reduction space, which not only speed up the computation of large independent sets drastically, but also enabled us to compute high-quality independent sets on much larger instances than previously reported in the literature.
Christian Schulz is currently a visiting researcher at the TU Wien and a postdoctoral researcher at the Karlsruhe Institute of Technology (KIT). He obtained his master degrees in mathematics and computer science as well as his Ph.D with summa cum laude at the KIT. He was the best student of the year 2010 of the faculty of informatics of the KIT and received multiple awards for his dissertation. His graph partitioning algorithms -- KaHIP -- have been able to improve or reproduce most of the benchmark entries in the Walshaw Benchmark and scored most of the points in the 10'th DIMACS Implementation Challenge on Graph Partitioning and Clustering.
This talk is organized by the Vienna PhD School of Informatics.