Given a graph \(G = (V,\!E)\) with \(n\) vertices and \(m\) edges, the Dominating Set problem asks for a set \(\mathcal{D} \subseteq V\) of minimal cardinality such that every vertex either is in \(D\) or adjacent to a member of \(D\). Although there is little hope for a kernelization algorithm on general graphs due to the W[2]-hardness of Dominating Set, data reduction rules are extensively used in practice.

Exploiting symmetry is a well-established technique to eliminate redundant work in combinatorial solvers, yet it often incurs computational overhead that limits its practical impact. In particular, practical instances arising from applications are frequently large and give rise to graphs whose size becomes a major bottleneck for algorithms dealing with symmetry. We propose a method for symmetry-preserving graph compression that reduces graph size while preserving the symmetries of the original graph in a controlled way. Our approach identifies and merges equivalent vertex colors under conditions that guarantee the recoverability of all symmetries. We provide both a theoretical foundation and efficient practical criteria for such merges, show that computing optimal and approximately optimal compression is intractable, and introduce a linear-time, practical heuristic. Extensive experiments on a vast library of graphs demonstrate that our new technique achieves significant compression ratios. Implemented in the state-of-the-art symmetry detection tool dejavu, we achieve an overall speedup of 1.39, with large modern SAT and MIP benchmarks benefiting the most.

We consider a maximum entropy edge weight model that allows for negative weights. Given a graph $G$ and possible weights $\mathcal{W}$ typically consisting of positive and negative values, the model selects edge weights $w \in \mathcal{W}^m$ uniformly at random from all weights that do not introduce a negative cycle. We propose an MCMC process and show that it converges to the required distribution. We then engineer an implementation of the process using a dynamic version of Johnson's algorithm in connection with a bidirectional Dijkstra search as well as an innovative resampling method. We empirically study the performance characteristics of these novel sampling algorithms as well as the output produced by the model.

Supplementary Material of "No Time to Interact: Simulating Population Protocols at Scale" / ESA2026. Please also check https://codeberg.org/manpen/graph-based-pop-prot-sim for updates.

A graph is called a $(k,ρ)$-graph iff every node can reach $ρ$ of its nearest neighbors in at most k hops. This property proved useful in the analysis and design of parallel shortest-path algorithms. Any graph can be transformed into a $(k,ρ)$-graph by adding shortcuts. Formally, the $(k,ρ)$-Minimum-Shortcut problem asks to find an appropriate shortcut set of minimal cardinality. We show that the $(k,ρ)$-Minimum-Shortcut problem is NP-complete in the practical regime of $k \ge 3$ and $ρ= Θ(n^ε)$ for $ε> 0$. With a related construction, we bound the approximation factor of known $(k,ρ)$-Minimum-Shortcut problem heuristics from below and propose algorithmic countermeasures improving the approximation quality. Further, we describe an integer linear problem (ILP) solving the $(k,ρ)$-Minimum-Shortcut problem optimally. Finally, we compare the practical performance and quality of all algorithms in an empirical campaign.

Preferential attachment lies at the heart of many network models aiming to replicate features of real world networks. To simulate the attachment process, conduct statistical tests, or obtain input data for benchmarks, efficient algorithms are required that are capable of generating large graphs according to these models. Existing graph generators are optimized for the most simple model, where new nodes that arrive in the network are connected to earlier nodes with a probability P(h) ∝ d that depends linearly on the degree d of the earlier node h. Yet, some networks are better explained by a more general attachment probability P(h) ∝ f (d) for some function f : ℕ → ℝ. Here, the polynomial case f(d) = dα where α ∈ ℝ >0 is of particular interest. In this paper, we present efficient algorithms that generate graphs according to the more general models. We first design a simple yet optimal sequential algorithm for the polynomial model. We then parallelize the algorithm by identifying batches of independent samples and obtain a near-optimal speedup when adding many nodes. In addition, we present an I/O-efficient algorithm that can even be used for the fully general model. To showcase the efficiency and scalability of our algorithms, we conduct an experimental study and compare their performance to existing solutions. Funding This work was supported by the Deutsche Forschungsgemeinschaft (DFG) under grant ME 2088/5-1 (FOR 2975 — Algorithms, Dynamics, and Information Flow in Networks). Supplemental material The internal memory algorithms are maintained at https://github.com/massive-graphs/nonlinear-preferential-attachment. The implementation of the dynamic weighted sampling data structure of [28] is independently maintained as the Rust crate https://crates.io/crates/dynamic-weighted-index. The external memory algorithms are available at https://github.com/massive-graphs/extmem-nlpa. An archive containing the frozen source code of all experiments and most of the raw data collected can be found on https://zenodo.org/record/7318118. * Link to full version: https://arxiv.org/abs/2211.06884

We consider the following common network analysis problem: given a degree sequence d = (d1,…, dn) ∈ ℕn return a uniform sample from the ensemble of all simple graphs with matching degrees. In practice, the problem is typically solved using Markov Chain Monte Carlo approaches, such as Edge-Switching or Curveball, even if no practical useful rigorous bounds are known on their mixing times. In contrast, Arman et al. sketch INC-PoWERLAW, a novel and much more involved algorithm capable of generating graphs for power-law bounded degree sequences with γ ⪆ 2.88 in expected linear time. For the first time, we give a complete description of the algorithm and add novel switchings. To the best of our knowledge, our open-source implementation of INC-POWERLAW is the first practical generator with rigorous uniformity guarantees for the aforementioned degree sequences. In an empirical investigation, we find that for small average-degrees INC-POWERLAW is very efficient and generates graphs with one million nodes in less than a second. For larger average-degrees, parallelism can partially mitigate the increased running-time.

The uniform sampling of simple graphs matching a prescribed degree sequence is an important tool in network science, e.g., to construct graph generators or null-models. Here, the Edge Switching Markov Chain (ES-MC) is a common choice. Given an arbitrary simple graph with the required degree sequence, ES-MC carries out a large number of small changes involving at most four edges to eventually obtain a uniform sample. In practice, reasonably short runs efficiently yield approximate uniform samples. We first engineer a simple sequential ES-MC implementation representing the graph in a hash-set. Despite its simplicity and to the best of our knowledge, our implementation significantly outperforms all openly available solutions. Secondly, we propose the Global Edge Switching Markov Chain (G-ES-MC) and show that it, too, converges to a uni-form distribution. We provide empirical evidence that G-ES-MC requires not more switches than ES-MC (and often fewer). Thirdly, we engineer shared-memory parallel algorithms for ES-MC and G-ES-MC; we find that they benefit from the easier dependency structure of the G-ES-MC. In an empirical evaluation, we demonstrate the scalability of our implementations.

The group testing problem asks for efficient pooling schemes and inference algorithms that allow to screen moderately large numbers of samples for rare infections. The goal is to accurately identify the infected individuals while minimizing the number of tests. We propose the novel adaptive pooling scheme adaptive Belief Propagation (ABP) that acknowledges practical limitations such as limited pooling sizes and noisy tests that may give imperfect answers. We demonstrate that the accuracy of ABP surpasses that of individual testing despite using few overall tests. The new design comes with Belief Propagation as an efficient inference algorithm. While the development of ABP is guided by mathematical analyses and asymptotic insights, we conduct an experimental study to obtain results on practical population sizes.

Recent advances in noiseless non-adaptive group testing have led to a precise asymptotic characterization of the number of tests required for high-probability recovery in the sublinear regime$k = n^{\theta }$(with$\theta \in (0,1)$), with$n$individuals among which$k$are infected. However, the required number of tests may increase substantially under real-world practical constraints, notably including bounds on the maximum number$\Delta $of tests an individual can be placed in, or the maximum number$\Gamma $of individuals in a given test. While previous works have given recovery guarantees for these settings, significant gaps remain between the achievability and converse bounds. In this paper, we substantially or completely close several of the most prominent gaps. In the case of$\Delta $-divisible items, we show that the definite defectives (DD) algorithm coupled with a random regular design is asymptotically optimal in dense scaling regimes, and optimal to within a factor of e more generally; we establish this by strengthening both the best known achievability and converse bounds. In the case of$\Gamma $-sized tests, we provide a comprehensive analysis of the regime$\Gamma = \Theta (1)$, and again establish a precise threshold proving the asymptotic optimality of SCOMP (a slight refinement of DD) equipped with a tailored pooling scheme. Finally, for each of these two settings, we provide near-optimal adaptive algorithms based on sequential splitting, and provably demonstrate gaps between the performance of optimal adaptive and non-adaptive algorithms.

We empirically investigate algorithms for solving Connected Components in the external memory model. In particular, we study whether the randomized O(Sort(E)) algorithm by Karger, Klein, and Tarjan can be implemented to compete with practically promising and simpler algorithms having only slightly worse theoretical cost, namely Borůvka’s algorithm and the algorithm by Sibeyn and collaborators. For all algorithms, we develop and test a number of tuning options. Our experiments are executed on a large set of different graph classes including random graphs, grids, geometric graphs, and hyperbolic graphs. Among our findings are: The Sibeyn algorithm is a very strong contender due to its simplicity and due to an added degree of freedom in its internal workings when used in the Connected Components setting. With the right tunings, the Karger-Klein-Tarjan algorithm can be implemented to be competitive in many cases. Higher graph density seems to benefit Karger-Klein-Tarjan relative to Sibeyn. Borůvka’s algorithm is not competitive with the two others.

We consider the efficient simulation of population protocols. In the population model, we are given a system of n agents modeled as identical finite-state machines. In each step, two agents are selected uniformly at random to interact by updating their states according to a common transition function. We empirically and analytically analyze two classes of simulators for this model. First, we consider sequential simulators executing one interaction after the other. Key to the performance of these simulators is the data structure storing the agents' states. For our analysis, we consider plain arrays, binary search trees, and a novel Dynamic Alias Table data structure. Secondly, we consider batch processing to efficiently update the states of multiple independent agents in one step. For many protocols considered in literature, our simulator requires amortized sub-constant time per interaction and is fast in practice: given a fixed time budget, the implementation of our batched simulator is able to simulate population protocols several orders of magnitude larger compared to the sequential competitors, and can carry out 2^50 interactions among the same number of agents in less than 400s.

We initiate a study of algorithms with a focus on the computational complexity of individual elements, and introduce the fragile complexity of comparison-based algorithms as the maximal number of comparisons any individual element takes part in. We give a number of upper and lower bounds on the fragile complexity for fundamental problems, including Minimum, Selection, Sorting and Heap Construction. The results include both deterministic and randomized upper and lower bounds, and demonstrate a separation between the two settings for a number of problems. The depth of a comparator network is a straight-forward upper bound on the worst case fragile complexity of the corresponding fragile algorithm. We prove that fragile complexity is a different and strictly easier property than the depth of comparator networks, in the sense that for some problems a fragile complexity equal to the best network depth can be achieved with less total work and that with randomization, even a lower fragile complexity is possible.

Hyperbolic random graphs (HRG) and geometric inhomogeneous random graphs (GIRG) are two similar generative network models that were designed to resemble complex real world networks. In particular, they have a power-law degree distribution with controllable exponent beta, and high clustering that can be controlled via the temperature T. We present the first implementation of an efficient GIRG generator running in expected linear time. Besides varying temperatures, it also supports underlying geometries of higher dimensions. It is capable of generating graphs with ten million edges in under a second on commodity hardware. The algorithm can be adapted to HRGs. Our resulting implementation is the fastest sequential HRG generator, despite the fact that we support non-zero temperatures. Though non-zero temperatures are crucial for many applications, most existing generators are restricted to T = 0. We also support parallelization, although this is not the focus of this paper. Moreover, we note that our generators draw from the correct probability distribution, i.e., they involve no approximation. Besides the generators themselves, we also provide an efficient algorithm to determine the non-trivial dependency between the average degree of the resulting graph and the input parameters of the GIRG model. This makes it possible to specify the desired expected average degree as input. Moreover, we investigate the differences between HRGs and GIRGs, shedding new light on the nature of the relation between the two models. Although HRGs represent, in a certain sense, a special case of the GIRG model, we find that a straight-forward inclusion does not hold in practice. However, the difference is negligible for most use cases.

Bidirectional compression algorithms work by substituting repeated substrings by references that, unlike in the famous LZ77-scheme, can point to either direction. We present such an algorithm that is particularly suited for an external memory implementation. We evaluate it experimentally on large data sets of size up to 128 GiB (using only 16 GiB of RAM) and show that it is significantly faster than all known LZ77 compressors, while producing a roughly similar number of factors. We also introduce an external memory decompressor for texts compressed with any uni- or bidirectional compression scheme.

Graph randomisation is a crucial task in the analysis and synthesis of networks. It is typically implemented as an edge switching process (ESMC) repeatedly swapping the nodes of random edge pairs while maintaining the degrees involved. Curveball is a novel approach that instead considers the whole neighbourhoods of randomly drawn node pairs. Its Markov chain converges to a uniform distribution, and experiments suggest that it requires less steps than the established ESMC. Since trades however are more expensive, we study Curveball's practical runtime by introducing the first efficient Curveball algorithms: the I/O-efficient EM-CB for simple undirected graphs and its internal memory pendant IM-CB. Further, we investigate global trades processing every node in a graph during a single super step, and show that undirected global trades converge to a uniform distribution and perform superior in practice. We then discuss EM-GCB and EM-PGCB for global trades and give experimental evidence that EM-PGCB achieves the quality of the state-of-the-art ESMC algorithm EM-ES nearly one order of magnitude faster.

LFR is a popular benchmark graph generator used to evaluate community detection algorithms. We present EM-LFR, the first external memory algorithm able to generate massive complex networks following the LFR benchmark. Its most expensive component is the generation of random graphs with prescribed degree sequences which can be divided into two steps: the graphs are first materialized deterministically using the Havel-Hakimi algorithm, and then randomized. Our main contributions are EM-HH and EM-ES, two I/O-efficient external memory algorithms for these two steps. In an experimental evaluation we demonstrate their performance: our implementation is able to handle graphs with more than 37 billion edges on a single machine, is competitive with a massive parallel distributed algorithm, and is faster than a state-of-the-art internal memory implementation even on instances fitting in main memory. EM-LFR's implementation is capable of generating large graph instances orders of magnitude faster than the original implementation. We give evidence that both implementations yield graphs with matching properties by applying clustering algorithms to generated instances.

Random graph models, originally conceived to study the structure of networks and the emergence of their properties, have become an indispensable tool for experimental algorithmics. Amongst them, hyperbolic random graphs form a well-accepted family, yielding realistic complex networks while being both mathematically and algorithmically tractable. We introduce two generators MemGen and HyperGen for the G_{alpha,C}(n) model, which distributes n random points within a hyperbolic plane and produces m=n*d/2 undirected edges for all point pairs close by; the expected average degree d and exponent 2*alpha+1 of the power-law degree distribution are controlled by alpha>1/2 and C. Both algorithms emit a stream of edges which they do not have to store. MemGen keeps O(n) items in internal memory and has a time complexity of O(n*log(log n) + m), which is optimal for networks with an average degree of d=Omega(log(log n)). For realistic values of d=o(n / log^{1/alpha}(n)), HyperGen reduces the memory footprint to O([n^{1-alpha}*d^alpha + log(n)]*log(n)). In an experimental evaluation, we compare HyperGen with four generators among which it is consistently the fastest. For small d=10 we measure a speed-up of 4.0 compared to the fastest publicly available generator increasing to 29.6 for d=1000. On commodity hardware, HyperGen produces 3.7e8 edges per second for graphs with 1e6 < m < 1e12 and alpha=1, utilising less than 600MB of RAM. We demonstrate nearly linear scalability on an Intel Xeon Phi.

Random graphs as mathematical models of massive scale-free networks have recently become very popular. While a number of interesting properties of them have been proven, huge instances of such networks actually need to be generated for experimental evaluation and to provide artificial data sets. In this paper, we consider generation methods for random graph models based on linear preferential attachment under limited computational resources and investigate our techniques using the well-known Barabási-Albert (BA) graph model. We present the first two I/O-efficient BA generators, MP-BA and TFP-BA, for the external-memory (EM) model and then extend MP-BA to massive parallelism based on but not limited to GPGPU. Our simple and easily generalizable sequential TFP-BA outperforms a highly tuned implementation of the sequential linear-time BB-BA algorithm by Batagelj and Brandes by several orders of magnitude once the graph size exceeds the available RAM by only 2%. An implementation of MP-BA targeting heterogeneous systems with CPUs and GPUs is 17.6 times faster than BB-BA for instances fitting in main memory and scales well in the EM setting. Both schemes support a number of features in more general preferential attachment models, e.g., seed graphs exceeding main memory, vertices with random initial degrees, the uniform sampling of vertices, directed graphs and edges between two randomly chosen vertices. Compared with previous studies on computer clusters, MP-BA yields competitive results and already poses a viable alternative using only a single machine.