The Temporal Graph Exploration problem (TEXP) takes as input a temporal graph, i.e., a sequence of graphs \((G_i)_{i\in\mathbb N}\) on the same vertex set, and asks for a walk of shortest length visiting all vertices, where the \(i\)-th step uses an edge from \(G_i\) or stays put. If each such \(G_i\) is connected, then an exploration of length \(n^2\) exists, and this is known to be the best possible up to a constant. More fine-grained lower and upper bounds have been obtained for restricted temporal graph classes, however, for several fundamental classes, a large gap persists between known bounds, and it remains unclear which properties of a temporal graph make it inherently difficult to explore.

We study variants of the (1+1) EA with heavy-tailed mutation operators in discrete optimization on an n-dimensional integer space. By combining heavy-tailed and concentrated distributions for both dimension selection and step size, we develop two novel variants: singly and doubly heavy-tailed mutators. Through experiments on integer-valued ONEMAX, integer-valued HURDLE, and a non-linear resource allocation problem, we demonstrate that these variants offer significant performance improvements. The singly heavy-tailed variant excels at escaping local optima, while the doubly heavy-tailed variant shows superior performance on complex non-linear problems.

We study high-dimensional random geometric graphs (RGGs) of edge-density $p$ with vertices uniformly distributed on the $d$-dimensional torus and edges inserted between \say{sufficiently close} vertices with respect to an $L_q$-norm. In this setting, we focus on distinguishing an RGG from an Erdős–Rényi graph if both models have the same marginal edge probability $p$. So far, most results in the literature considered either spherical RGGs with $L_2$-distance or toroidal RGGs under $L_\infty$-distance. However, for general $L_q$-distances, many questions remain open, especially if $p$ is allowed to depend on $n$. The main reason for this is that RGGs under $L_q$-distances can not easily be represented as the logical \say{AND} of their 1-dimensional counterparts, as is the case for $L_\infty$ geometries. To overcome this difficulty, we devise a novel technique for quantifying the dependence between edges based on a modified version of Edgeworth expansions. Our technique yields the first tight algorithmic upper bounds for distinguishing toroidal RGGs under general $L_q$ norms from Erdős–Rényi graphs for any fixed $p$ and $q$. We achieve this by showing that the signed triangle statistic can distinguish the two models when $d\ll n^3p^3$ for the whole regime of edge probabilities $\frac{c}{n} Cite this Paper BibTeX @InProceedings{pmlr-v291-baguley25a, title = {Testing Thresholds and Spectral Properties of High-Dimensional Random Toroidal Graphs via Edgeworth-Style Expansions}, author = {Baguley, Samuel and G{\"o}bel, Andreas and Pappik, Marcus and Schiller, Leon}, booktitle = {Proceedings of Thirty Eighth Conference on Learning Theory}, pages = {200--201}, year = {2025}, editor = {Haghtalab, Nika and Moitra, Ankur}, volume = {291}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--04 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v291/main/assets/baguley25a/baguley25a.pdf}, url = {https://proceedings.mlr.press/v291/baguley25a.html}, abstract = {We study high-dimensional random geometric graphs (RGGs) of edge-density $p$ with vertices uniformly distributed on the $d$-dimensional torus and edges inserted between \say{sufficiently close} vertices with respect to an $L_q$-norm. In this setting, we focus on distinguishing an RGG from an Erdős–Rényi graph if both models have the same marginal edge probability $p$. So far, most results in the literature considered either spherical RGGs with $L_2$-distance or toroidal RGGs under $L_\infty$-distance. However, for general $L_q$-distances, many questions remain open, especially if $p$ is allowed to depend on $n$. The main reason for this is that RGGs under $L_q$-distances can not easily be represented as the logical \say{AND} of their 1-dimensional counterparts, as is the case for $L_\infty$ geometries. To overcome this difficulty, we devise a novel technique for quantifying the dependence between edges based on a modified version of Edgeworth expansions. Our technique yields the first tight algorithmic upper bounds for distinguishing toroidal RGGs under general $L_q$ norms from Erdős–Rényi graphs for any fixed $p$ and $q$. We achieve this by showing that the signed triangle statistic can distinguish the two models when $d\ll n^3p^3$ for the whole regime of edge probabilities $\frac{c}{n} Copy to Clipboard Download Endnote %0 Conference Paper %T Testing Thresholds and Spectral Properties of High-Dimensional Random Toroidal Graphs via Edgeworth-Style Expansions %A Samuel Baguley %A Andreas Göbel %A Marcus Pappik %A Leon Schiller %B Proceedings of Thirty Eighth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2025 %E Nika Haghtalab %E Ankur Moitra %F pmlr-v291-baguley25a %I PMLR %P 200--201 %U https://proceedings.mlr.press/v291/baguley25a.html %V 291 %X We study high-dimensional random geometric graphs (RGGs) of edge-density $p$ with vertices uniformly distributed on the $d$-dimensional torus and edges inserted between \say{sufficiently close} vertices with respect to an $L_q$-norm. In this setting, we focus on distinguishing an RGG from an Erdős–Rényi graph if both models have the same marginal edge probability $p$. So far, most results in the literature considered either spherical RGGs with $L_2$-distance or toroidal RGGs under $L_\infty$-distance. However, for general $L_q$-distances, many questions remain open, especially if $p$ is allowed to depend on $n$. The main reason for this is that RGGs under $L_q$-distances can not easily be represented as the logical \say{AND} of their 1-dimensional counterparts, as is the case for $L_\infty$ geometries. To overcome this difficulty, we devise a novel technique for quantifying the dependence between edges based on a modified version of Edgeworth expansions. Our technique yields the first tight algorithmic upper bounds for distinguishing toroidal RGGs under general $L_q$ norms from Erdős–Rényi graphs for any fixed $p$ and $q$. We achieve this by showing that the signed triangle statistic can distinguish the two models when $d\ll n^3p^3$ for the whole regime of edge probabilities $\frac{c}{n} Copy to Clipboard Download APA Baguley, S., Göbel, A., Pappik, M. & Schiller, L.. (2025). Testing Thresholds and Spectral Properties of High-Dimensional Random Toroidal Graphs via Edgeworth-Style Expansions. Proceedings of Thirty Eighth Conference on Learning Theory, in Proceedings of Machine Learning Research 291:200-201 Available from https://proceedings.mlr.press/v291/baguley25a.html. Copy to Clipboard Download Related Material Download PDF This site last compiled Sun, 05 Jul 2026 15:03:27 +0000 Github Account Copyright © The authors and PMLR 2026. MLResearchPress

Hyperbolic random graphs inherit many properties that are present in real-world networks. The hyperbolic geometry imposes a scale-free network with a strong clustering coefficient. Other properties like a giant component, the small world phenomena and others follow. This motivates the design of simple algorithms for hyperbolic random graphs. In this paper we consider threshold hyperbolic random graphs (HRGs). Greedy heuristics are commonly used in practice as they deliver a good approximations to the optimal solution even though their theoretical analysis would suggest otherwise. A typical example for HRGs are degeneracy-based greedy algorithms [Bläsius, Fischbeck; Transactions of Algorithms '24]. In an attempt to bridge this theory-practice gap we characterise the parameter of degeneracy yielding a simple approximation algorithm for colouring HRGs. The approximation ratio of our algorithm ranges from (2/√3) to 4/3 depending on the power-law exponent of the model. We complement our findings for the degeneracy with new insights on the clique number of hyperbolic random graphs. We show that degeneracy and clique number are substantially different and derive an improved upper bound on the clique number. Additionally, we show that the core of HRGs does not constitute the largest clique. Lastly we demonstrate that the degeneracy of the closely related standard model of geometric inhomogeneous random graphs behaves inherently different compared to the one of hyperbolic random graphs.

Abstract Parameterized analysis provides powerful mechanisms for obtaining fine-grained insights into different types of algorithms. In this work, we combine this field with evolutionary algorithms and provide parameterized complexity analysis of evolutionary multi-objective algorithms for the W-separator problem, which is a natural generalization of the vertex cover problem. The goal is to remove the minimum number of vertices such that each connected component in the resulting graph has at most W vertices. We provide different multi-objective formulations involving two or three objectives that provably lead to fixed-parameter evolutionary algorithms with respect to the value of an optimal solution OPT and W. Of particular interest are kernelizations and the reducible structures used for them. We show that in expectation the algorithms make incremental progress in finding such structures and beyond. The current best known kernelization of the W-separator uses linear programming methods and requires non-trivial post-processing steps to extract the reducible structures. We provide additional structural features to show that evolutionary algorithms with appropriate objectives are also capable of extracting them. Our results show that evolutionary algorithms with different objectives guide the search and admit fixed parameterized runtimes to solve or approximate (even arbitrarily close) the W-separator problem.

Parameterized analysis provides powerful mechanisms for obtaining fine-grained insights into different types of algorithms. In this work, we combine this field with evolutionary algorithms and provide parameterized complexity analysis of evolutionary multiobjective algorithms for the W-separator problem, which is a natural generalization of the vertex cover problem. The goal is to remove the minimum number of vertices such that each connected component in the resulting graph has at most W vertices. We provide different multi-objective formulations involving two or three objectives that provably lead to fixed-parameter evolutionary algorithms with respect to the value of an optimal solution OPT and W. Of particular interest are kernelizations and the reducible structures used for them. We show that in expectation the algorithms make incremental progress in finding such structures and beyond. The current best known kernelization of the W-separator uses linear programming methods and requires a non-trivial post-process to extract the reducible structures. We provide additional structural features to show that evolutionary algorithms with appropriate objectives are also capable of extracting them. Our results show that evolutionary algorithms with different objectives guide the search and admit fixed parameterized runtimes to solve or approximate (even arbitrarily close) the W-separator problem.

Combinatorial optimization problems are a prominent application area of evolutionary algorithms, where the (1+1) EA is one of the most investigated. We extend this algorithm by introducing some problem knowledge with a specialized mutation operator which works under the assumption that the number of 1s of a solution is critical, as frequently happens in combinatorial optimization. This slight modification increases the chance to correct wrongly placed bits while preserving the simplicity and problem independence of the (1+1) EA.