The number one criticism of average-case analysis is that we do not actually know the probability distribution of real-world inputs. Thus, analyzing an algorithm on some random model has no implications for practical performance. At its core, this criticism doubts the existence of external validity ; i.e., it assumes that algorithmic behavior on the somewhat simple and clean models does not translate beyond the models to practical performance real-world input. With this article, we provide a first step toward studying the question of external validity systematically. To this end, we evaluate the performance of six graph algorithms on a collection of 2,740 sparse real-world networks depending on two properties: heterogeneity (variance in the degree distribution) and locality (tendency of edges to connect vertices that are already close). We compare this with the performance on generated networks with varying locality and heterogeneity. We find that the performance in the idealized setting of network models translates surprisingly well to real-world networks. Moreover, heterogeneity and locality appear to be the core properties impacting the performance of many graph algorithms.

The Single-Source Shortest Path problem is classically solved by applying Dijkstra's algorithm. However, the plain version of this algorithm is far too slow for real-world applications such as routing in large road networks. To amend this, many speed-up techniques have been developed that build on the idea of computing auxiliary data in a preprocessing phase, that is used to speed up the queries. One well-known example is the Arc-Flags algorithm that is based on the idea of precomputing edge flags to make the search more goal-directed. To explain the strong practical performance of such speed-up techniques, several graph parameters have been introduced. The skeleton dimension is one such parameter that has already been used to derive runtime bounds for some speed-up techniques. Moreover, it was experimentally shown to be low in real-world road networks.

Abstract The computational complexity of the VertexCover problem has been studied extensively. Most notably, it is NP-complete to find an optimal solution and typically NP-hard to find an approximation with reasonable factors. In contrast, recent experiments suggest that on many real-world networks the run time to solve VertexCover is way smaller than even the best known FPT-approaches can explain. We link these observations to two properties that are observed in many real-world networks, namely a heterogeneous degree distribution and high clustering. To formalize these properties and explain the observed behavior, we analyze how a branch-and-reduce algorithm performs on hyperbolic random graphs, which have become increasingly popular for modeling real-world networks. In fact, we are able to show that the VertexCover problem on hyperbolic random graphs can be solved in polynomial time, with high probability. The proof relies on interesting structural properties of hyperbolic random graphs. Since these predictions of the model are interesting in their own right, we conducted experiments on real-world networks showing that these properties are also observed in practice.

Traffic congestion is a major issue that can be solved by suggesting drivers alternative routes they are willing to take. This concept has been formalized as a strategic routing problem in which a single alternative route is suggested to an existing one. We extend this formalization and introduce the multiple-routes (MRs) problem, which is given a start and destination and aims at finding up to$n$different routes that the drivers strategically disperse over, minimizing the overall travel time of the system. Due to theNP-hard nature of the problem, we introduce the MRs evolutionary algorithm (MREA) as a heuristic solver. We study several mutation and crossover operators and evaluate them on real-world data of Berlin, Germany. We find that a combination of all operators yields the best result, reducing the overall travel time by a factor between 1.8 and 3, in the median, compared to all drivers taking the fastest route. 6mm]Please cite reference[2]in the text of the paper. It was removed from the abstract as having reference in an abstract is contrary to IEEE journal style.For the base case$n=2$, we compare our MREA to the highly tailored optimal solver by Bläsius et al. (2020), and show that, in the median, our approach finds solutions of quality at least 99.69% of an optimal solution while only requiring 40% of the time.

Here you find supplemental material for our paper On the External Validity of Average-Case Analyses of Graph Algorithms. Code The source code and a description of how to use it can be found at github.com/thobl/external-validity. Additionally external-validity-main.zip contains a snapshot. Docker Image The easiest way to reproduce the experiments is to use the docker image ext-val.zip. Refer to github.com/thobl/external-validity for instructions how to use it. Input Data: Networks from Network Repository We use a set of 3006 networks from networkrepository.com [1]. Refer to our paper for more details on the data set. [1] Ryan A. Rossi and Nesreen K. Ahmed, The Network Data Repository with Interactive Graph Analytics and Visualization (AAAI 2015) Here we provide this data set in two formats. Use the first for reproducing our experiments. If you want to do your own experiments on the same networks, we recommend using the second. input_data.zip contains the original graph as edge list (one edge per line) with no guarantees on where node indices start (usually at 0 or 1) or whether they are consecutive. The graphs might consist of multiple connected components. edge_lists_real.zip contains the graphs reduced to their largest connected component. Node indices are consecutive starting at 0 and every edge is contained only for one direction. Output Data: Generated Networks The generated networks are provided as edge lists (one connected component, consecutive node indices starting at 0, every edge is contained only in one direction). They are grouped into different categories. For more details on the generated networks, refer to our paper. cl stands for Chung-Lu graphs er stands for Erdős-Rényi graphs deg_20 indicates that the average degree is 20, otherwise it is 10 girg stands for geometric inhomogeneous random graphs girg_square means that a square was used as ground space, otherwise a torus was used girg_deg_scaling contains girgs with various average degrees Output Data: Computation Results The raw data computed by our experiments is contained in output_data.zip. Additionally, there are three csv files summarizing all computed statistics for the networks. graph_stats.csv contains the stats for all graphs graph_stats_real.csv contains the same stats but only for the graphs from Network Repository graph_stats_gen.csv contains stats for the generated networks, including the parameters used to generate them

Abstract We present fully polynomial time approximation schemes for a broad class of Holant problems with complex edge weights, which we call Holant polynomials. We transform these problems into partition functions of abstract combinatorial structures known as polymers in statistical physics. Our method involves establishing zero-free regions for the partition functions of polymer models and using the most significant terms of the cluster expansion to approximate them. Results of our technique include new approximation and sampling algorithms for a diverse class of Holant polynomials in the low-temperature regime (i.e. small external field) and approximation algorithms for general Holant problems with small signature weights. Additionally, we give randomised approximation and sampling algorithms with faster running times for more restrictive classes. Finally, we improve the known zero-free regions for a perfect matching polynomial.

Traffic congestion is a major issue that can be solved by suggesting drivers alternative routes they are willing to take. This concept has been formalized as a strategic routing problem in which a single alternative route is suggested to an existing one. We extend this formalization and introduce the Multiple-Routes problem, which is given a start and destination and aims at finding up to n different routes that the drivers strategically disperse over, minimizing the overall travel time of the system.

The cluster editing problem is to transform an input graph into a cluster graph by performing a minimum number of edge editing operations. A cluster graph is a graph where each connected component is a clique. An edit operation can be either adding a new edge or removing an existing edge. In this write-up we outline the core techniques used in the exact cluster editing algorithm of the KaPoCE framework (contains also a heuristic solver), submitted to the exact track of the 2021 PACE challenge.

The cluster editing problem is to transform an input graph into a cluster graph by performing a minimum number of edge editing operations. A cluster graph is a graph where each connected component is a clique. An edit operation can be either adding a new edge or removing an existing edge. In this write-up we outline the core techniques used in the heuristic cluster editing algorithm of the Karlsruhe and Potsdam Cluster Editing (KaPoCE) framework, submitted to the heuristic track of the 2021 PACE challenge.

Traditional navigation services find the fastest route for a single driver. Though always using the fastest route seems desirable for every individual, selfish behavior can have undesirable effects such as higher energy consumption and avoidable congestion, even leading to higher overall and individual travel times. In contrast, strategic routing aims at optimizing the traffic for all agents regarding a global optimization goal. We introduce a framework to formalize real-world strategic routing scenarios as algorithmic problems and study one of them, which we call Single Alternative Path (SAP), in detail. There, we are given an original route between a single origin--destination pair. The goal is to suggest an alternative route to all agents that optimizes the overall travel time under the assumption that the agents distribute among both routes according to a psychological model, for which we introduce the concept of Pareto-conformity. We show that the SAP problem is NP-complete, even for such models. Nonetheless, assuming Pareto-conformity, we give multiple algorithms for different variants of SAP, using multi-criteria shortest path algorithms as subroutines. Moreover, we prove that several natural models are in fact Pareto-conform. The implementation of our algorithms serves as a proof of concept, showing that SAP can be solved in reasonable time even though the algorithms have exponential running time in the worst case.

Island models in evolutionary computation solve problems by a careful interplay of independently running evolutionary algorithms on the island and an exchange of good solutions between the islands. In this work, we conduct rigorous run time analyses for such island models trying to simultaneously obtain good run times and low communication effort.