At COSEAL 2026, Maryam Gholami Shiri presented the paper “Graph Instance Landscapes: When Structural Similarity Does (Not) Reflect Shortest-Path Performance.”

The presented work investigates how structural properties of graph instances relate to the runtime behavior of shortest-path algorithms. Traditional benchmarking of shortest-path methods is typically performed through aggregate performance analysis over heterogeneous graph collections, which often obscures how algorithms react to specific structural characteristics of instances. To address this, the study adopts an instance-landscape perspective by embedding graph instances into a low-cost structural feature space and grouping them into regions of similar structure.

The analysis covers three representative benchmark families: weighted Erdős–Rényi graphs, random geometric (wireless) graphs, and real-world road networks. The study evaluates four shortest-path paradigms, including Dijkstra, Bidirectional Dijkstra, A*, and DEQ-based approaches, enabling a detailed comparison of algorithmic behavior across structurally distinct graph regions.

An important finding of the work is that structural similarity in feature space does not necessarily imply similar runtime performance. Even graphs belonging to the same structural region can exhibit significantly different runtime characteristics. Furthermore, the merged analysis of benchmark suites shows that different graph families occupy largely disjoint structural regions, emphasizing the importance of benchmark diversity in shortest-path algorithm evaluation.

The work contributes toward more structure-aware and explainable benchmarking methodologies, highlighting both the opportunities and limitations of using graph landscapes to understand algorithm performance.