High-Performance Graph Algorithms

Motivation

Graphs (or networks) are a powerful abstraction of various phenomena that can be expressed as relations between entities. As such graph algorithms have been the subject of many research efforts. Recently, however, we see a qualitative change how graph algorithms are used in practice. This change is due to (i) the complex structures and the sizes of graphs in emerging applications and (ii) the computer systems on which graph problems are solved. Application areas driving this change are diverse. To name a few, consider microblogging services in social media, bioinformatics, routing in traffic networks, technology diffusion and decentralized trade in economics, and combinatorial scientific computing. These application areas have in common that the associated problem instances show massive scale and irregular or skewed distributions of structural and semantic properties of entities and their interactions.

We need novel algorithms to cope with the ever growing problem sizes. A major challenge in designing and implementing graph algorithms is the large gap between theoretical computational models and observed performances. Computer architectures are becoming increasingly parallel and heterogeneous. Yet, many design and analysis techniques focus on the sequential case, and many striking theoretical results do not transfer to efficient computational tools. To fully exploit emerging architectures, it is important to develop parallel algorithms and tools with the specific hardware in mind.

This Dagstuhl Seminar aims at narrowing the gap between theoretical and practical graph algorithms. To this end, we would like to bring together (i) theoretical computer scientists whose works have strong practical context, (ii) researchers from graph-focused high performance computing, and (iii) algorithm engineers whose work falls in between the two previous areas. The invited practitioners in graph algorithms will also represent the domain expertise in applications and high-performance tools that address real-life graph problems. Two areas of high-performance graph algorithms that we plan to focus on are algorithmic network analysis and combinatorial scientific computing.

We would like to discuss and achieve some of the synergies that become possible from bringing the aforementioned fields closer together. One open research question covered will be how to transfer provably efficient theoretical methods into code that runs efficiently on modern parallel hardware. By bringing together experts from different fields, we hope to develop the next-generation tools of the trade for large graphs. These tools ideally are significantly faster and more feature-rich than the current state of the art, more closely connected with recent theoretical breakthroughs, and have more simplified development processes. This, in turn, will allow domain scientists to process larger data sets more effectively, and allow them to tackle problems previously out of reach.

Some topics for which we expect joint interest include (but are not limited to): solvers for graph-induced (non)linear systems of equations, I/O and communication efficiency of graph algorithms, fast analysis of massive complex networks, worst-case complexity vs empirical running time of graph algorithms, combinatorial scientific computing, and accelerating numerical methods for graphs.