Recent years have been exceptionally fruitful for graph algorithms, yielding major theoretical advancements for fundamental problems like maximum flow, matching, and single-source shortest paths. Despite this progress, a significant gap persists between the asymptotic efficiency of these novel algorithms and their practical utility. Many of these breakthroughs, while theoretically powerful, are either too complex to implement reliably or are hindered by large constant factors and sub-polynomial terms hidden within their complexity analysis. For example, an algorithm with O(n log¹⁰ n) complexity, while asymptotically superior to one with O(n²) running time, is likely outperformed for any practical input size.

This Dagstuhl Seminar directly addresses this theory-practice gap by exploring an alternative approach to algorithm design—one that integrates practical considerations from the very beginning. The goal is to bring together algorithm researchers, algorithm engineers, and practitioners to foster a holistic perspective on algorithm development. We aim to create a forum where theorists can present concepts ripe for implementation and where engineers can highlight real-world bottlenecks that require new theoretical insights.

The seminar’s core topics will cover the entire lifecycle of practical algorithm development. Discussions will center on:

• Design Principles: Moving beyond pure asymptotic analysis to consider metrics like implementation simplicity, low constant factors, and amenability to modern hardware architectures, including cache efficiency and parallelizability.
• Implementation Strategies: Addressing the challenges of translating complex theoretical constructs into robust, high-performance code, and exploring best practices for optimization and debugging.
• Evaluation Methodologies: Establishing rigorous standards for empirical analysis and benchmarking to enable fair comparisons and a clear understanding of an algorithm's true performance characteristics.

By facilitating exchange between different communities, this Dagstuhl Seminar aims to accelerate the creation of the next generation of truly practical and impactful graph algorithms.

Creative Commons BY 4.0

Jakub Lacki, Danupon Nanongkai, Christian Schulz, and Blair D. Sullivan