Graph Instance Landscapes: When Structural Similarity Does (Not) Reflect Shortest-Path Performance (opens in new tab)

Benchmarking shortest-path algorithms is commonly based on aggregate performance over heterogeneous graph sets, which limits insight into how different search paradigms react to instance structure. We adopt an instance-landscape view of graph benchmarking by embedding graphs into a low-cost structural feature space and clustering them into regions of similar structure. Three benchmark suites are studied: weighted Erd\H{o}s--R\'enyi graphs, rando...