Bläsius, Thomas; Fischbeck, Philipp On the External Validity of Average-Case Analyses of Graph AlgorithmsACM Transactions on Algorithms 2024
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 paper, we provide a first step towards studying the question of external validity systematically. To this end, we evaluate the performance of six graph algorithms on a collection of 2740 sparse real-world networks depending on two properties; the 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.
Casel, Katrin; Friedrich, Tobias; Neubert, Stefan; Schmid, Markus L. Shortest distances as enumeration problemDiscrete Applied Mathematics 2024: 89–103
We investigate the single source shortest distance (SSSD) and all pairs shortest distance (APSD) problems as enumeration problems (on unweighted and integer weighted graphs), meaning that the elements (u,v,d(u,v)) – where u and v are vertices with shortest distance d(u,v) – are produced and listed one by one without repetition. The performance is measured in the RAM model of computation with respect to preprocessing time and delay, i.e., the maximum time that elapses between two consecutive outputs. This point of view reveals that specific types of output (e.g., excluding the non-reachable pairs (u,v,∞), or excluding the self-distances (u,u,0)) and the order of enumeration (e.g., sorted by distance, sorted row-wise with respect to the distance matrix) have a huge impact on the complexity of APSD while they appear to have no effect on SSSD. In particular, we show for APSD that enumeration without output restrictions is possible with delay in the order of the average degree. Excluding non-reachable pairs, or requesting the output to be sorted by distance, increases this delay to the order of the maximum degree. Further, for weighted graphs, a delay in the order of the average degree is also not possible without preprocessing or considering self-distances as output. In contrast, for SSSD we find that a delay in the order of the maximum degree without preprocessing is attainable and unavoidable for any of these requirements.
Sauer, Pascal; Cseh, Ágnes; Lenzner, Pascal Improving ranking quality and fairness in Swiss-system chess tournamentsJournal of Quantitative Analysis in Sports 2024
Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, Anna Geometric Network Creation GamesSIAM Journal on Discrete Mathematics 2024: 277–315
Network creation games are a well-known approach for explaining and analyzing the structure, quality, and dynamics of real-world networks that evolved via the interaction of selfish agents without a central authority. In these games selfish agents corresponding to nodes in a network strategically buy incident edges to improve their centrality. However, past research on these games only considered the creation of networks with unit-weight edges. In practice, e.g., when constructing a fiber-optic network, the choice of which nodes to connect and also the induced price for a link crucially depend on the distance between the involved nodes, and such settings can be modeled via edge-weighted graphs. We incorporate arbitrary edge weights by generalizing the well-known model by Fabrikant et al. [Proceedings of PODC ’03, ACM, 2003, pp. 347–351] to edge-weighted host graphs and focus on the geometric setting where the weights are induced by the distances in some metric space. In stark contrast to the state of the art for the unit-weight version, where the price of anarchy is conjectured to be constant and where resolving this is a major open problem, we prove a tight nonconstant bound on the price of anarchy for the metric version and a slightly weaker upper bound for the nonmetric case. Moreover, we analyze the existence of equilibria, the computational hardness, and the game dynamics for several natural metrics. The model we propose can be seen as the game-theoretic analogue of the classical network design problem. Thus, low-cost equilibria of our game correspond to decentralized and stable approximations of the optimum network design.
Jana, Satyabrata; Saha, Souvik; Sahu, Abhishek; Saurabh, Saket; Verma, Shaily Partitioning subclasses of chordal graphs with few deletionsTheoretical Computer Science 2024: 114288
In the (Vertex) \(k\)-Way Cut problem, input is an undirected graph \(G\), an integer \(s\), and the goal is to find a subset \(S\) of edges (vertices) of size at most \(s\), such that \(G-S\) has at least \(k\) connected components. Downey et al. [Electr. Notes Theor. Comput. Sci. 2003] showed that \(k\)-Way Cut is W[1]-hard parameterized by \( k \). However, Kawarabayashi and Throup [FOCS 2011] showed that the problem is fixed-parameter tractable (FPT) in general graphs with respect to the parameter \(s\) and provided a \( \mathcal{O(s^s^\mathcal{O(s) n^2) \) time algorithm, where \(n \) denotes the number of vertices in \(G \). The best-known algorithm for this problem runs in time \(s^{\mathcal{O(s) n^\mathcal{O(1)}\) given by Lokshtanov et al. [ACM Tran. of Algo. 2021]. On the other hand, Vertex \(k\)-Way Cut is W[1]-hard with respect to either of the parameters, \(k\) or \(s\) or \(k+s\). These algorithmic results motivate us to look at the problems on special classes of graphs. In this paper, we consider the (Vertex) \(k\)-Way Cut problem on subclasses of chordal graphs and obtain the following results. We first give a sub-exponential FPT algorithm for \(k\)-Way Cut running in time \(2^{\mathcal{O(\sqrt{s} \log s) n^\mathcal{O(1)}\) on chordal graphs. It is known that Vertex \(k\)-Way Cut is W[1]-hard on chordal graphs, in fact on split graphs, parameterized by \(k+s\). We complement this hardness result by designing polynomial-time algorithms for Vertex \(k\)-Way Cut on interval graphs, circular-arc graphs and permutation graphs.
Friedrich, Tobias; Göbel, Andreas; Klodt, Nicolas; Krejca, Martin S.; Pappik, Marcus The Irrelevance of Influencers: Information Diffusion with Re-Activation and Immunity Lasts Exponentially Long on Social Network ModelsAnnual AAAI Conference on Artificial Intelligence 2024
Information diffusion models on networks are at the forefront of AI research. The dynamics of such models typically follow stochastic models from epidemiology, used to model not only infections but various phenomena, including the behavior of computer viruses and viral marketing campaigns. A core question in this setting is how to efficiently detect the most influential vertices in the host graph such that the infection survives the longest. In processes that incorporate re-infection of the vertices, such as the SIS process, theoretical studies identify parameter thresholds where the survival time of the process rapidly transitions from logarithmic to super-polynomial. These results contradict the intuition that the starting configuration is relevant, since the process will always either die out fast or survive almost indefinitely. A shortcoming of these results is that models incorporating short-term immunity (or creative advertisement fatigue) have not been subjected to such a theoretical analysis so far. We reduce this gap in the literature by studying the SIRS process, a more realistic model, which besides re-infection additionally incorporates short-term immunity. On complex network models, we identify parameter regimes for which the process survives exponentially long, and we get a tight threshold for random graphs. Underlying these results is our main technical contribution, showing a threshold behavior for the survival time of the SIRS process on graphs with large expander subgraphs, such as social network models.
Fomin, Fedor V.; Golovach, Petr A.; Sagunov, Danil; Simonov, Kirill Tree Containment Above Minimum Degree is FPTSymposium on Discrete Algorithms (SODA) 2024: 366–376
Abstract According to the classic Chvatal's Lemma from 1977, a graph of minimum degree \(\delta(G)\) contains every tree on \(\delta(G)+1\) vertices. Our main result is the following algorithmic “extension” of Chvatal's Lemma: For any \(n\)-vertex graph G, integer \(k\), and a tree \(T\) on at most \(\delta(G)+k\) vertices, deciding whether \(G\) contains a subgraph isomorphic to \(T\), can be done in time \(f(k) · n^\mathcal{O(1)}\) for some function \(f\) of \(k\) only. The proof of our main result is based on an interplay between extremal graph theory and parameterized algorithms. The full version of the paper can be accessed at https://arxiv.org/abs/2310.09678.
Bläsius, Thomas; Cohen, Sarel; Fischbeck, Philipp; Friedrich, Tobias; Krejca, Martin S. Robust Parameter Fitting to Realistic Network Models via Iterative Stochastic ApproximationCoRR 2024
ArXiv preprint
Random graph models are widely used to understand network properties and graph algorithms. Key to such analyses are the different parameters of each model, which affect various network features, such as its size, clustering, or degree distribution. The exact effect of the parameters on these features is not well understood, mainly because we lack tools to thoroughly investigate this relation. Moreover, the parameters cannot be considered in isolation, as changing one affects multiple features. Existing approaches for finding the best model parameters of desired features, such as a grid search or estimating the parameter-feature relations, are not well suited, as they are inaccurate or computationally expensive. We introduce an efficient iterative fitting method, named ParFit, that finds parameters using only a few network samples, based on the Robbins-Monro algorithm. We test ParFit on three well-known graph models, namely Erdős-Rényi, Chung-Lu, and geometric inhomogeneous random graphs, as well as on real-world networks, including web networks. We find that ParFit performs well in terms of quality and running time across most parameter configurations.
