2025

Bals, Ben; Döring, Michelle; Klodt, Nicolas; Skretas, George Dynamic Network Discovery via Infection Tracing 2025
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Researchers, policy makers, and engineers need to make sense of data from spreading processes as diverse as rumor spreading in social networks, viral infections, and water contamination. Classical questions include predicting infection behavior in a given network or deducing the network structure from infection data. Most of the research on network infections studies static graphs, that is, the connections in the network are assumed to not change. More recently, temporal graphs, in which connections change over time, have been used to more accurately represent real-world infections, which rarely occur in unchanging networks. We propose a model for temporal graph discovery that is consistent with previous work on static graphs and embraces the greater expressiveness of temporal graphs. For this model, we give algorithms and lower bounds which are often tight. We analyze different variations of the problem, which make our results widely applicable and it also clarifies which aspects of temporal infections make graph discovery easier or harder. We round off our analysis with an experimental evaluation of our algorithm on real-world interaction data from the Stanford Network Analysis Project and on temporal Erdős-Renyi graphs. On Erdős-Renyi graphs, we uncover a threshold behavior, which can be explained by a novel connectivity parameter that we introduce during our theoretical analysis.
@inproceedings{bals_DynamicNetwork_2025, abstract = {Researchers, policy makers, and engineers need to make sense of data from spreading processes as diverse as rumor spreading in social networks, viral infections, and water contamination. Classical questions include predicting infection behavior in a given network or deducing the network structure from infection data. Most of the research on network infections studies static graphs, that is, the connections in the network are assumed to not change. More recently, temporal graphs, in which connections change over time, have been used to more accurately represent real-world infections, which rarely occur in unchanging networks. We propose a model for temporal graph discovery that is consistent with previous work on static graphs and embraces the greater expressiveness of temporal graphs. For this model, we give algorithms and lower bounds which are often tight. We analyze different variations of the problem, which make our results widely applicable and it also clarifies which aspects of temporal infections make graph discovery easier or harder. We round off our analysis with an experimental evaluation of our algorithm on real-world interaction data from the Stanford Network Analysis Project and on temporal Erdős-Renyi graphs. On Erdős-Renyi graphs, we uncover a threshold behavior, which can be explained by a novel connectivity parameter that we introduce during our theoretical analysis.}, author = {Bals, Ben and Döring, Michelle and Klodt, Nicolas and Skretas, George}, keywords = {random ijcai nicolasklodt spreadingprocess benbals temporalgraphs year2025 michelledoering networkdiscovery masterthesis georgeskretas}, title = {Dynamic Network Discovery via Infection Tracing}, year = 2025 }

Schmidt, Jonas; Verma, Shaily; Mallek, Nadym A Parameterized Study of Secluded Structures in Directed Graphs 2025: 53:1–53:21
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Given an undirected graph G and an integer k, the Secluded \Pi-Subgraph problem asks you to find a maximum size induced subgraph that satisfies a property \Pi and has at most k neighbors in the rest of the graph. This problem has been extensively studied; however, there is no prior study of the problem in directed graphs. This question has been mentioned by Jansen et al. [ISAAC'23]. In this paper, we initiate the study of Secluded Subgraph problem in directed graphs by incorporating different notions of neighborhoods: in-neighborhood, out-neighborhood, and their union. Formally, we call these problems \{\text{In}, \text{Out}, \text{Total}\}-Secluded \Pi-Subgraph, where given a directed graph G and integers k, we want to find an induced subgraph satisfying \Pi of maximum size that has at most k in/out/total-neighbors in the rest of the graph, respectively. We investigate the parameterized complexity of these problems for different properties \Pi. In particular, we prove the following parameterized results: - We design an FPT algorithm for the Total-Secluded Strongly Connected Subgraph problem when parameterized by k. - We show that the In/Out-Secluded \mathcal{F}-Free Subgraph problem with parameter k+w is W[1]-hard, where \mathcal{F} is a family of directed graphs except any subgraph of a star graph whose edges are directed towards the center. This result also implies that In/Out-Secluded DAG is W[1]-hard, unlike the undirected variants of the two problems, which are FPT. - We design an FPT-algorithm for In/Out/Total-Secluded \alpha-Bounded Subgraph when parameterized by k, where \alpha-bounded graphs are a superclass of tournaments. - For undirected graphs, we improve the best-known FPT algorithm for Secluded Clique by providing a faster FPT algorithm that runs in time 1.6181^kn^{\mathcal{O}(1)}.
@inproceedings{svm-apsossidg-2025, abstract = {Given an undirected graph G and an integer k, the Secluded \Pi-Subgraph problem asks you to find a maximum size induced subgraph that satisfies a property \Pi and has at most k neighbors in the rest of the graph. This problem has been extensively studied; however, there is no prior study of the problem in directed graphs. This question has been mentioned by Jansen et al. [ISAAC'23]. In this paper, we initiate the study of Secluded Subgraph problem in directed graphs by incorporating different notions of neighborhoods: in-neighborhood, out-neighborhood, and their union. Formally, we call these problems \{\text{In}, \text{Out}, \text{Total}\}-Secluded \Pi-Subgraph, where given a directed graph G and integers k, we want to find an induced subgraph satisfying \Pi of maximum size that has at most k in/out/total-neighbors in the rest of the graph, respectively. We investigate the parameterized complexity of these problems for different properties \Pi. In particular, we prove the following parameterized results: - We design an FPT algorithm for the Total-Secluded Strongly Connected Subgraph problem when parameterized by k. - We show that the In/Out-Secluded \mathcal{F}-Free Subgraph problem with parameter k+w is W[1]-hard, where \mathcal{F} is a family of directed graphs except any subgraph of a star graph whose edges are directed towards the center. This result also implies that In/Out-Secluded DAG is W[1]-hard, unlike the undirected variants of the two problems, which are FPT. - We design an FPT-algorithm for In/Out/Total-Secluded \alpha-Bounded Subgraph when parameterized by k, where \alpha-bounded graphs are a superclass of tournaments. - For undirected graphs, we improve the best-known FPT algorithm for Secluded Clique by providing a faster FPT algorithm that runs in time 1.6181^kn^{\mathcal{O}(1)}.}, author = {Schmidt, Jonas and Verma, Shaily and Mallek, Nadym}, keywords = {sys:relevantfor:ae isaac shailyverma year2025 jonasschmidt nadymmallek}, pages = {53:1–53:21}, title = {A Parameterized Study of Secluded Structures in Directed Graphs}, year = 2025 }

Deligkas, Argyrios; Döring, Michelle; Eiben, Eduard; Goldsmith, Tiger-Lily; Skretas, George; Tennigkeit, Georg How Many Lines to Paint the City: Exact Edge-Cover in Temporal GraphsProceedings of the AAAI Conference on Artificial Intelligence 2025: 26498–26506
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Logistics and transportation networks require a large amount of resources to realise necessary connections between locations and minimizing these resources is a vital aspect of planning research. Since such networks have dynamic connections that are only available at specific times, intricate models are needed to portray them accurately. In this paper, we study the problem of minimizing the number of resources needed to realise a dynamic network, using the temporal graphs model. In a temporal graph, edges appear at specific points in time. Given a temporal graph and a natural number k, we ask whether we can cover every temporal edge exactly once using at most k temporal journeys; in a temporal journey consecutive edges have to adhere to the order of time. We conduct a thorough investigation of the complexity of the problem with respect to four dimensions: (a) whether the type of the temporal journey is a walk, a trail, or a path; (b) whether the chronological order of edges in the journey is strict or non-strict; (c) whether the temporal graph is directed or undirected; (d) whether the start and end points of each journey are given. We almost completely resolve the complexity of these problems and provide dichotomies for each of them with respect to k.
@inproceedings{deligkas_HowMany_2025, abstract = {Logistics and transportation networks require a large amount of resources to realise necessary connections between locations and minimizing these resources is a vital aspect of planning research. Since such networks have dynamic connections that are only available at specific times, intricate models are needed to portray them accurately. In this paper, we study the problem of minimizing the number of resources needed to realise a dynamic network, using the temporal graphs model. In a temporal graph, edges appear at specific points in time. Given a temporal graph and a natural number k, we ask whether we can cover every temporal edge exactly once using at most k temporal journeys; in a temporal journey consecutive edges have to adhere to the order of time. We conduct a thorough investigation of the complexity of the problem with respect to four dimensions: (a) whether the type of the temporal journey is a walk, a trail, or a path; (b) whether the chronological order of edges in the journey is strict or non-strict; (c) whether the temporal graph is directed or undirected; (d) whether the start and end points of each journey are given. We almost completely resolve the complexity of these problems and provide dichotomies for each of them with respect to k.}, author = {Deligkas, Argyrios and Döring, Michelle and Eiben, Eduard and Goldsmith, Tiger-Lily and Skretas, George and Tennigkeit, Georg}, journal = {Proceedings of the AAAI Conference on Artificial Intelligence}, keywords = {argyriosdeligkas tigerlilygoldsmith parameterizedcomplexity pathcover eduardeiben aaai michelledoering georgtennigkeit temporalpathgraph exactedge-cover temporalpathumber temporalgraphs year2025 reachability georgeskretas}, month = {Apr.}, number = 25, pages = {26498-26506}, title = {How Many Lines to Paint the City: Exact Edge-Cover in Temporal Graphs}, volume = 39, year = 2025 }

Doerr, Benjamin; Krejca, Martin S.; Rudolph, Günter Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer SpacesAnnual AAAI Conference on Artificial Intelligence (AAAI) 2025: 26955–26963
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Randomized search heuristics have been applied successfully to a plethora of problems. This success is complemented by a large body of theoretical results. Unfortunately, the vast majority of these results regard problems with binary or continuous decision variables -- the theoretical analysis of randomized search heuristics for unbounded integer domains is almost nonexistent. To resolve this shortcoming, we start the runtime analysis of multi-objective evolutionary algorithms, which are among the most successful randomized search heuristics, for unbounded integer search spaces. We analyze single- and full-dimensional mutation operators with three different mutation strengths, namely changes by plus/minus one (unit strength), random changes following a law with exponential tails, and random changes following a power-law. The performance guarantees we prove on a recently proposed natural benchmark problem suggest that unit mutation strengths can be slow when the initial solutions are far from the Pareto front. When setting the expected change right (depending on the benchmark parameter and the distance of the initial solutions), the mutation strength with exponential tails yields the best runtime guarantees in our results -- however, with a wrong choice of this expectation, the performance guarantees quickly become highly uninteresting. With power-law mutation, which is an essentially parameter-less mutation operator, we obtain good results uniformly over all problem parameters and starting points. We complement our mathematical findings with experimental results that suggest that our bounds are not always tight. Most prominently, our experiments indicate that power-law mutation outperforms the one with exponential tails even when the latter uses a near-optimal parametrization. Hence, we suggest to favor power-law mutation for unknown problems in integer spaces.
@inproceedings{doerr2025runtime, abstract = {Randomized search heuristics have been applied successfully to a plethora of problems. This success is complemented by a large body of theoretical results. Unfortunately, the vast majority of these results regard problems with binary or continuous decision variables – the theoretical analysis of randomized search heuristics for unbounded integer domains is almost nonexistent. To resolve this shortcoming, we start the runtime analysis of multi-objective evolutionary algorithms, which are among the most successful randomized search heuristics, for unbounded integer search spaces. We analyze single- and full-dimensional mutation operators with three different mutation strengths, namely changes by plus/minus one (unit strength), random changes following a law with exponential tails, and random changes following a power-law. The performance guarantees we prove on a recently proposed natural benchmark problem suggest that unit mutation strengths can be slow when the initial solutions are far from the Pareto front. When setting the expected change right (depending on the benchmark parameter and the distance of the initial solutions), the mutation strength with exponential tails yields the best runtime guarantees in our results – however, with a wrong choice of this expectation, the performance guarantees quickly become highly uninteresting. With power-law mutation, which is an essentially parameter-less mutation operator, we obtain good results uniformly over all problem parameters and starting points. We complement our mathematical findings with experimental results that suggest that our bounds are not always tight. Most prominently, our experiments indicate that power-law mutation outperforms the one with exponential tails even when the latter uses a near-optimal parametrization. Hence, we suggest to favor power-law mutation for unknown problems in integer spaces.}, author = {Doerr, Benjamin and Krejca, Martin S. and Rudolph, Günter}, booktitle = {Annual AAAI Conference on Artificial Intelligence (AAAI)}, keywords = {guenterrudolph martinskrejca aaai benjamindoerr year2025 solelyextern}, pages = {26955-26963}, title = {Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces}, year = 2025 }

Doerr, Benjamin; Ivan, Tudor; Krejca, Martin S. Speeding Up the NSGA-II With a Simple Tie-Breaking RuleAnnual AAAI Conference on Artificial Intelligence (AAAI) 2025: 26964–26972
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The non-dominated sorting genetic algorithm II (NSGA-II) is the most popular multi-objective optimization heuristic. Recent mathematical runtime analyses have detected two shortcomings in discrete search spaces, namely, that the NSGA-II has difficulties with more than two objectives and that it is very sensitive to the choice of the population size. To overcome these difficulties, we analyze a simple tie-breaking rule in the selection of the next population. Similar rules have been proposed before, but have found only little acceptance. We prove the effectiveness of our tie-breaking rule via mathematical runtime analyses on the classic OneMinMax, LeadingOnesTrailingZeros, and OneJumpZeroJump benchmarks. We prove that this modified NSGA-II can optimize the three benchmarks efficiently also for many objectives, in contrast to the exponential lower runtime bound previously shown for OneMinMax with three or more objectives. For the bi-objective problems, we show runtime guarantees that do not increase when moderately increasing the population size over the minimum admissible size. For example, for the OneJumpZeroJump problem with representation length $n$ and gap parameter $k$, we show a runtime guarantee of $O(\max\{n^{k+1},Nn\})$ function evaluations when the population size is at least four times the size of the Pareto front. For population sizes larger than the minimal choice $N = \Theta(n)$, this result improves considerably over the $\Theta(Nn^k)$ runtime of the classic NSGA-II.
@inproceedings{doerr2025speeding, abstract = {The non-dominated sorting genetic algorithm II (NSGA-II) is the most popular multi-objective optimization heuristic. Recent mathematical runtime analyses have detected two shortcomings in discrete search spaces, namely, that the NSGA-II has difficulties with more than two objectives and that it is very sensitive to the choice of the population size. To overcome these difficulties, we analyze a simple tie-breaking rule in the selection of the next population. Similar rules have been proposed before, but have found only little acceptance. We prove the effectiveness of our tie-breaking rule via mathematical runtime analyses on the classic OneMinMax, LeadingOnesTrailingZeros, and OneJumpZeroJump benchmarks. We prove that this modified NSGA-II can optimize the three benchmarks efficiently also for many objectives, in contrast to the exponential lower runtime bound previously shown for OneMinMax with three or more objectives. For the bi-objective problems, we show runtime guarantees that do not increase when moderately increasing the population size over the minimum admissible size. For example, for the OneJumpZeroJump problem with representation length $n$ and gap parameter $k$, we show a runtime guarantee of $O(\max\{n^{k+1},Nn\})$ function evaluations when the population size is at least four times the size of the Pareto front. For population sizes larger than the minimal choice $N = \Theta(n)$, this result improves considerably over the $\Theta(Nn^k)$ runtime of the classic NSGA-II.}, author = {Doerr, Benjamin and Ivan, Tudor and Krejca, Martin S.}, booktitle = {Annual AAAI Conference on Artificial Intelligence (AAAI)}, keywords = {tudorivan martinskrejca aaai benjamindoerr year2025 solelyextern}, pages = {26964-26972}, title = {Speeding Up the NSGA-II With a Simple Tie-Breaking Rule}, year = 2025 }

Krogmann, Simon; Lenzner, Pascal; Skopalik, Alexander The Bakers and Millers Game with Restricted LocationsAutonomous Agents and Multiagent Systems (AAMAS) 2025
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
We study strategic location choice by customers and sellers, termed the Bakers and Millers Game in the literature. In our generalized setting, each miller can freely choose any location for setting up a mill, while each baker is restricted in the choice of location for setting up a bakery. For optimal bargaining power, a baker would like to select a location with many millers to buy flour from and with little competition from other bakers. Likewise, a miller aims for a location with many bakers and few competing millers. Thus, both types of agents choose locations to optimize the ratio of agents of opposite type divided by agents of the same type at their chosen location. Originally raised in the context of Fractional Hedonic Games, the Bakers and Millers Game has applications that range from commerce to product design. We study the impact of location restrictions on the properties of the game. While pure Nash equilibria trivially exist in the setting without location restrictions, we show via a sophisticated, efficient algorithm that even the more challenging restricted setting admits equilibria. Moreover, the computed equilibrium approximates the optimal social welfare by a factor of at most \(2\left(\frac{e}{e-1}\right)\). Furthermore, we give tight bounds on the price of anarchy/stability. On the conceptual side, the location choice feature adds a new layer to Hedonic Games, in the sense that agents that select the same location form a coalition. This allows to naturally restrict the possible coalitions that can be formed. With this, our model generalizes simple symmetric Fractional Hedonic Games on complete bipartite valuation graphs and also Hedonic Diversity Games with utilities single-peaked at 0. We believe that this generalization is also a very interesting direction for other types of Hedonic Games.
@inproceedings{krogmann2025bakers, abstract = {We study strategic location choice by customers and sellers, termed the Bakers and Millers Game in the literature. In our generalized setting, each miller can freely choose any location for setting up a mill, while each baker is restricted in the choice of location for setting up a bakery. For optimal bargaining power, a baker would like to select a location with many millers to buy flour from and with little competition from other bakers. Likewise, a miller aims for a location with many bakers and few competing millers. Thus, both types of agents choose locations to optimize the ratio of agents of opposite type divided by agents of the same type at their chosen location. Originally raised in the context of Fractional Hedonic Games, the Bakers and Millers Game has applications that range from commerce to product design. We study the impact of location restrictions on the properties of the game. While pure Nash equilibria trivially exist in the setting without location restrictions, we show via a sophisticated, efficient algorithm that even the more challenging restricted setting admits equilibria. Moreover, the computed equilibrium approximates the optimal social welfare by a factor of at most \(2\left(\frac{e}{e-1}\right)\). Furthermore, we give tight bounds on the price of anarchy/stability. On the conceptual side, the location choice feature adds a new layer to Hedonic Games, in the sense that agents that select the same location form a coalition. This allows to naturally restrict the possible coalitions that can be formed. With this, our model generalizes simple symmetric Fractional Hedonic Games on complete bipartite valuation graphs and also Hedonic Diversity Games with utilities single-peaked at 0. We believe that this generalization is also a very interesting direction for other types of Hedonic Games.}, author = {Krogmann, Simon and Lenzner, Pascal and Skopalik, Alexander}, booktitle = {Autonomous Agents and Multiagent Systems (AAMAS)}, keywords = {year2025 aamas simonkrogmann pascallenzner alexanderskopalik}, title = {The Bakers and Millers Game with Restricted Locations}, year = 2025 }

de la Haye, Merlin; Lenzner, Pascal; Schmand‎, Daniel; Schröder‎, Nicole Network Creation Games with 2-Neighborhood MaximizationInternational Conference on Algorithms and Complexity (CIAC) 2025: 18–34
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Network creation games are well-established for investigating the decentralized formation of communication networks, like the Internet or social networks. In these games, selfish agents that correspond to network nodes strategically create costly edges to maximize their centrality in the formed network. We depart from this by focusing on the simpler objective of maximizing the 2-neighborhood. This seems natural for social networks, as an agent's connection benefit is typically provided by her neighbors and their neighbors but not by strangers further away. For this natural model, we study the existence, the structure and the quality both of Nash equilibria (NE) and greedy equilibria (GE). We give structural results on the existence of degree-2 paths and cycles, and we provide tight constant bounds on the diameter. In contrast to most previous network creation game research, our bounds on the diameter are independent of edge cost \(\alpha\) and the number of agents \(n\). Also, bounding the diameter does not imply bounding the price of anarchy, which calls for other methods. Using them, we obtain non-trivial bounds on the price of anarchy, including a \(\Omega\left(\log\left(\frac{n}{\alpha}\right)\right)\) lower bound for NE, and a tight linear bound for GE for low \(\alpha\). Keywords: Network Creation Games, Social Networks, Structure of Equilibria, Price of Anarchy, Diameter, Network Density
@inproceedings{dlHLSS2025-NCGTwoNeighborhood, abstract = {Network creation games are well-established for investigating the decentralized formation of communication networks, like the Internet or social networks. In these games, selfish agents that correspond to network nodes strategically create costly edges to maximize their centrality in the formed network. We depart from this by focusing on the simpler objective of maximizing the 2-neighborhood. This seems natural for social networks, as an agent's connection benefit is typically provided by her neighbors and their neighbors but not by strangers further away. For this natural model, we study the existence, the structure and the quality both of Nash equilibria (NE) and greedy equilibria (GE). We give structural results on the existence of degree-2 paths and cycles, and we provide tight constant bounds on the diameter. In contrast to most previous network creation game research, our bounds on the diameter are independent of edge cost \(\alpha\) and the number of agents \(n\). Also, bounding the diameter does not imply bounding the price of anarchy, which calls for other methods. Using them, we obtain non-trivial bounds on the price of anarchy, including a \(\Omega\left(\log\left(\frac{n}{\alpha}\right)\right)\) lower bound for NE, and a tight linear bound for GE for low \(\alpha\). Keywords: Network Creation Games, Social Networks, Structure of Equilibria, Price of Anarchy, Diameter, Network Density}, author = {de la Haye, Merlin and Lenzner, Pascal and Schmand‎, Daniel and Schröder‎, Nicole}, booktitle = {International Conference on Algorithms and Complexity (CIAC)}, editor = {Finocchi, Irene and Georgiadis, Loukas}, keywords = {nicoleschroeder CIAC danielschmand year2025 merlindelahaye pascallenzner}, pages = {18–34}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Network Creation Games with 2-Neighborhood Maximization}, volume = 15680, year = 2025 }

Niklanovits, Aikaterini; Simonov, Kirill; Verma, Shaily; Zeif, Ziena Connected Partitions via Connected Dominating SetsEuropean Symposium on Algorithms (ESA) 2025
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The classical theorem due to Gy\H{o}ri and Lov{á}sz states that any \(k\)-connected graph \(G\) admits a partition into \(k\) connected subgraphs, where each subgraph has a prescribed size and contains a prescribed vertex, as long as the total size of target subgraphs is equal to the size of \(G\). However, this result is notoriously evasive in terms of efficient constructions, and it is still unknown whether such a partition can be computed in polynomial time, even for \(k = 5\). We make progress towards an efficient constructive version of the Gy\H{o}ri--Lov{á}sz theorem by considering a natural strengthening of the \(k\)-connectivity requirement. Specifically, we show that the desired connected partition can be found in polynomial time, if \(G\) contains\(k\) disjoint connected dominating sets. As a consequence of this result, we give several efficient approximate and exact constructive versions of the original Gy\H{o}ri--Lov{á}sz theorem: \begin{itemize} \item On general graphs, a Gy\H{o}ri--Lov{á}sz partition with \(k\) parts can be computed in polynomial time when the input graph has connectivity \(\Omega(k \cdot \log^2 n)\); \item On convex bipartite graphs, connectivity of \(4k\) is sufficient; \item On biconvex graphs and interval graphs, connectivity of \(k\) is sufficient, meaning that our algorithm gives a ``true'' constructive version of the theorem on these graph classes. \end{itemize}
@inproceedings{DBLP:journals/corr/abs-2503-13112, abstract = {The classical theorem due to Gy\H{o}ri and Lov{á}sz states that any \(k\)-connected graph \(G\) admits a partition into \(k\) connected subgraphs, where each subgraph has a prescribed size and contains a prescribed vertex, as long as the total size of target subgraphs is equal to the size of \(G\). However, this result is notoriously evasive in terms of efficient constructions, and it is still unknown whether such a partition can be computed in polynomial time, even for \(k = 5\). We make progress towards an efficient constructive version of the Gy\H{o}ri–Lov{á}sz theorem by considering a natural strengthening of the \(k\)-connectivity requirement. Specifically, we show that the desired connected partition can be found in polynomial time, if \(G\) contains\(k\) disjoint connected dominating sets. As a consequence of this result, we give several efficient approximate and exact constructive versions of the original Gy\H{o}ri–Lov{á}sz theorem: \begin{itemize} \item On general graphs, a Gy\H{o}ri–Lov{á}sz partition with \(k\) parts can be computed in polynomial time when the input graph has connectivity \(\Omega(k \cdot \log^2 n)\); \item On convex bipartite graphs, connectivity of \(4k\) is sufficient; \item On biconvex graphs and interval graphs, connectivity of \(k\) is sufficient, meaning that our algorithm gives a ``true'' constructive version of the theorem on these graph classes. \end{itemize}}, author = {Niklanovits, Aikaterini and Simonov, Kirill and Verma, Shaily and Zeif, Ziena}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {sys:relevantfor:ae zienazeif esa kirillsimonov aikaterininiklanovits shailyverma year2025}, title = {Connected Partitions via Connected Dominating Sets}, year = 2025 }

Krejca, Martin S.; Neumann, Frank; Witt, Carsten Population Dynamics and Improved Runtime Guarantees for the (µ+1) EA on BinValFoundations of Genetic Algorithms (FOGA) 2025: 142–153
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Populations play a key role in the area of evolutionary computation to tackle complex optimization problems. Nevertheless, it is hard to understand the underlying population dynamics from a theoretical perspective, and only a limited number of theoretical results for population-based algorithms are available even for simple benchmark functions. In this paper, we study the classic \((1+1)\) EA on the benchmark problem BinVal, which allows for exponentially many function values. Previous methods for the analysis, based on fitness levels and multiplicative drift analysis, lead to runtime bounds for this function of size \(n\) that include an additive term of \(\Theta(n^2)\). We provide new insights into how this standard algorithm optimizes BinVal, and we provide runtime bounds that are polynomial in the population size \(\mu\) and do not include this additive term. In particular, we prove bounds on the expected runtime that are \(O(\mu^5 n\log(n/\mu^4))\) for standard bit mutation, which is \(O(n \log n)\) for constant \(\mu\). Our analysis considers the population dynamics of the \((1+1)\) EA more closely, proving that copies created by mutation lead to a low diversity in short blocks of bits across all individuals. We extend this method to mutation operators that cannot create duplicates, and prove bounds similar to standard bit mutation.
@inproceedings{krejca2025population, abstract = {Populations play a key role in the area of evolutionary computation to tackle complex optimization problems. Nevertheless, it is hard to understand the underlying population dynamics from a theoretical perspective, and only a limited number of theoretical results for population-based algorithms are available even for simple benchmark functions. In this paper, we study the classic \((1+1)\) EA on the benchmark problem BinVal, which allows for exponentially many function values. Previous methods for the analysis, based on fitness levels and multiplicative drift analysis, lead to runtime bounds for this function of size \(n\) that include an additive term of \(\Theta(n^2)\). We provide new insights into how this standard algorithm optimizes BinVal, and we provide runtime bounds that are polynomial in the population size \(\mu\) and do not include this additive term. In particular, we prove bounds on the expected runtime that are \(O(\mu^5 n\log(n/\mu^4))\) for standard bit mutation, which is \(O(n \log n)\) for constant \(\mu\). Our analysis considers the population dynamics of the \((1+1)\) EA more closely, proving that copies created by mutation lead to a low diversity in short blocks of bits across all individuals. We extend this method to mutation operators that cannot create duplicates, and prove bounds similar to standard bit mutation.}, author = {Krejca, Martin S. and Neumann, Frank and Witt, Carsten}, booktitle = {Foundations of Genetic Algorithms (FOGA)}, keywords = {foga martinskrejca carstenwitt year2025 frankneumann solelyextern}, pages = {142-153}, title = {Population Dynamics and Improved Runtime Guarantees for the (µ+1) EA on BinVal}, year = 2025 }

Aivasiliotis, Panagiotis; Göbel, Andreas; Roth, Marc; Schmitt, Johannes Parameterised Holant Problems52nd International Colloquium on Automata, Languages, and Programming (ICALP) 2025: 7:1–7:14
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We investigate the complexity of parameterised holant problems p-Holant(S) for families of symmetric signatures S. The parameterised holant framework has been introduced by Curticapean in 2015 as a counter-part to the classical and well-established theory of holographic reductions and algorithms, and it constitutes an extensive family of coloured and weighted counting constraint satisfaction problems on graph-like structures, encoding as special cases various well-studied counting problems in parameterised and fine-grained complexity theory such as counting edge-colourful k-matchings, graph-factors, Eulerian orientations or, more generally, subgraphs with weighted degree constraints. We establish an exhaustive complexity trichotomy along the set of signatures S: Depending on the signatures, p-Holant(S) is either (1) solvable in FPT-near-linear time, i.e., in time f(k)·Õ(|x|), or (2) solvable in “FPT-matrix-multiplication time”, i.e., in time f(k)·O(n^ω), where n is the number of vertices of the underlying graph, but not solvable in FPT-near-linear time, unless the Triangle Conjecture fails, or (3) #W[1]-complete and no significant improvement over the naive brute force algorithm is possible unless the Exponential Time Hypothesis fails. This classification reveals a significant and surprising gap in the complexity landscape of parameterised Holants: Not only is every instance either fixed-parameter tractable or #W[1]-complete, but additionally, every FPT instance is solvable in time (at most) f(k)·O(n^ω). We show that there are infinitely many instances of each of the types; for example, all constant signatures yield holant problems of type (1), and the problem of counting edge-colourful k-matchings modulo p is of type (p) for p ∈ {2,3}. Finally, we also establish a complete classification for a natural uncoloured version of parameterised holant problem p-UnColHolant(S), which encodes as special cases the non-coloured analogues of the aforementioned examples. We show that the complexity of p-UnColHolant(S) is different: Depending on S all instances are either solvable in FPT-near-linear time, or #W[1]-complete, that is, there are no instances of type (2).
@inproceedings{aivasiliotis2025parameterised, abstract = {We investigate the complexity of parameterised holant problems p-Holant(S) for families of symmetric signatures S. The parameterised holant framework has been introduced by Curticapean in 2015 as a counter-part to the classical and well-established theory of holographic reductions and algorithms, and it constitutes an extensive family of coloured and weighted counting constraint satisfaction problems on graph-like structures, encoding as special cases various well-studied counting problems in parameterised and fine-grained complexity theory such as counting edge-colourful k-matchings, graph-factors, Eulerian orientations or, more generally, subgraphs with weighted degree constraints. We establish an exhaustive complexity trichotomy along the set of signatures S: Depending on the signatures, p-Holant(S) is either (1) solvable in FPT-near-linear time, i.e., in time f(k)·Õ(|x|), or (2) solvable in “FPT-matrix-multiplication time”, i.e., in time f(k)·O(n^ω), where n is the number of vertices of the underlying graph, but not solvable in FPT-near-linear time, unless the Triangle Conjecture fails, or (3) #W[1]-complete and no significant improvement over the naive brute force algorithm is possible unless the Exponential Time Hypothesis fails. This classification reveals a significant and surprising gap in the complexity landscape of parameterised Holants: Not only is every instance either fixed-parameter tractable or #W[1]-complete, but additionally, every FPT instance is solvable in time (at most) f(k)·O(n^ω). We show that there are infinitely many instances of each of the types; for example, all constant signatures yield holant problems of type (1), and the problem of counting edge-colourful k-matchings modulo p is of type (p) for p ∈ {2,3}. Finally, we also establish a complete classification for a natural uncoloured version of parameterised holant problem p-UnColHolant(S), which encodes as special cases the non-coloured analogues of the aforementioned examples. We show that the complexity of p-UnColHolant(S) is different: Depending on S all instances are either solvable in FPT-near-linear time, or #W[1]-complete, that is, there are no instances of type (2).}, author = {Aivasiliotis, Panagiotis and Göbel, Andreas and Roth, Marc and Schmitt, Johannes}, booktitle = {52nd International Colloquium on Automata, Languages, and Programming (ICALP)}, keywords = {myown sys:relevantfor:ae panagiotisaivasiliotis friedrich}, pages = {7:1–7:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, title = {Parameterised Holant Problems}, volume = 334, year = 2025 }

Göbel, Andreas; Klodt, Nicolas; Krejca, Martin S.; Pappik, Marcus Resistance is Futile: Gradually Declining Immunity Retains the Exponential Duration of Immunity-Free DiffusionInternational Joint Conferences on Artifical Intelligence (IJCAI) 2025
[ Abstract ] [ BibTeX ] [ Download ]
 
Diffusion processes pervade numerous areas of AI, abstractly modeling the dynamics of exchanging, oftentimes volatile, information in networks. A central question is how long the information remains in the network, known as survival time. For the commonly studied SIS process, the expected survival time is at least super-polynomial in the network size already on star graphs, for a wide range of parameters. In contrast, the expected survival time of the SIRS process, which introduces temporary immunity, is always at most polynomial on stars and only known to be super-polynomial for far denser networks, such as expanders. However, this result relies on featuring full temporary immunity, which is not always present in actual processes. We introduce the cSIRS process, which incorporates gradually declining immunity such that the expected immunity at each point in time is identical to that of the SIRS process. We study the survival time of the cSIRS process rigorously on star graphs and expanders and show that its expected survival time is very similar to that of the SIS process, which features no immunity. This suggests that featuring gradually declining immunity is almost as having none at all.
@inproceedings{gbel2025resistance, abstract = {Diffusion processes pervade numerous areas of AI, abstractly modeling the dynamics of exchanging, oftentimes volatile, information in networks. A central question is how long the information remains in the network, known as survival time. For the commonly studied SIS process, the expected survival time is at least super-polynomial in the network size already on star graphs, for a wide range of parameters. In contrast, the expected survival time of the SIRS process, which introduces temporary immunity, is always at most polynomial on stars and only known to be super-polynomial for far denser networks, such as expanders. However, this result relies on featuring full temporary immunity, which is not always present in actual processes. We introduce the cSIRS process, which incorporates gradually declining immunity such that the expected immunity at each point in time is identical to that of the SIRS process. We study the survival time of the cSIRS process rigorously on star graphs and expanders and show that its expected survival time is very similar to that of the SIS process, which features no immunity. This suggests that featuring gradually declining immunity is almost as having none at all.}, author = {Göbel, Andreas and Klodt, Nicolas and Krejca, Martin S. and Pappik, Marcus}, booktitle = {International Joint Conferences on Artifical Intelligence (IJCAI)}, keywords = {ijcai nicolasklodt marcuspappik martinskrejca andreasgoebel year2025}, title = {Resistance is Futile: Gradually Declining Immunity Retains the Exponential Duration of Immunity-Free Diffusion}, year = 2025 }

Alghouass, Yasser; Doerr, Benjamin; Krejca, Martin S.; Lagmah, Mohammed Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-IIInternational Joint Conferences on Artifical Intelligence (IJCAI) 2025: 8833–8841
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Together with the NSGA-II and SMS-EMOA, the strength Pareto evolutionary algorithm 2 (SPEA2) is one of the most prominent dominance-based multi-objective evolutionary algorithms (MOEAs). Different from the NSGA-II, it does not employ the crowding distance (essentially the distance to neighboring solutions) to compare pairwise non-dominating solutions but a complex system of \(\sigma\)-distances that builds on the distances to all other solutions. In this work, we give a first mathematical proof showing that this more complex system of distances can be superior. More specifically, we prove that a simple steady-state SPEA2 can compute optimal approximations of the Pareto front of the OneMinMax benchmark in polynomial time. The best proven guarantee for a comparable variant of the NSGA-II only assures approximation ratios of roughly a factor of two, and both mathematical analyses and experiments indicate that optimal approximations are not found efficiently.
@inproceedings{alghouass2025proven, abstract = {Together with the NSGA-II and SMS-EMOA, the strength Pareto evolutionary algorithm 2 (SPEA2) is one of the most prominent dominance-based multi-objective evolutionary algorithms (MOEAs). Different from the NSGA-II, it does not employ the crowding distance (essentially the distance to neighboring solutions) to compare pairwise non-dominating solutions but a complex system of \(\sigma\)-distances that builds on the distances to all other solutions. In this work, we give a first mathematical proof showing that this more complex system of distances can be superior. More specifically, we prove that a simple steady-state SPEA2 can compute optimal approximations of the Pareto front of the OneMinMax benchmark in polynomial time. The best proven guarantee for a comparable variant of the NSGA-II only assures approximation ratios of roughly a factor of two, and both mathematical analyses and experiments indicate that optimal approximations are not found efficiently.}, author = {Alghouass, Yasser and Doerr, Benjamin and Krejca, Martin S. and Lagmah, Mohammed}, booktitle = {International Joint Conferences on Artifical Intelligence (IJCAI)}, keywords = {ijcai martinskrejca yasseralghouass mohammedlagmah benjamindoerr year2025 solelyextern}, pages = {8833-8841}, title = {Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-II}, year = 2025 }

Doerr, Benjamin; Krejca, Martin S.; Opris, Andre Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary AlgorithmInternational Joint Conferences on Artifical Intelligence (IJCAI) 2025: 8876–8884
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The global simple evolutionary multi-objective optimizer (GSEMO) is a simple, yet often effective multi-objective evolutionary algorithm (MOEA). By only maintaining non-dominated solutions, it has a variable population size that automatically adjusts to the needs of the optimization process. The downside of the dynamic population size is that the population dynamics of this algorithm are harder to understand, resulting, e.g., in the fact that only sporadic tight runtime analyses exist. In this work, we significantly enhance our understanding of the dynamics of the GSEMO, in particular, for the classic CountingOnesCountingZeros (COCZ) benchmark. From this, we prove a lower bound of order \(\Omega(n^2 \log n)\), for the first time matching the seminal upper bounds known for over twenty years. We also show that the GSEMO finds any constant fraction of the Pareto front in time \(O(n^2)\), improving over the previous estimate of \(O(n^2 \log n)\) for the time to find the first Pareto optimum. Our methods extend to other classic benchmarks and yield, e.g., the first \(\Omega(n^{k+1})\) lower bound for the OJZJ benchmark in the case that the gap parameter is \(k \in \{2,3\}\). We are therefore optimistic that our new methods will be useful in future mathematical analyses of MOEAs.
@inproceedings{doerr2025tight, abstract = {The global simple evolutionary multi-objective optimizer (GSEMO) is a simple, yet often effective multi-objective evolutionary algorithm (MOEA). By only maintaining non-dominated solutions, it has a variable population size that automatically adjusts to the needs of the optimization process. The downside of the dynamic population size is that the population dynamics of this algorithm are harder to understand, resulting, e.g., in the fact that only sporadic tight runtime analyses exist. In this work, we significantly enhance our understanding of the dynamics of the GSEMO, in particular, for the classic CountingOnesCountingZeros (COCZ) benchmark. From this, we prove a lower bound of order \(\Omega(n^2 \log n)\), for the first time matching the seminal upper bounds known for over twenty years. We also show that the GSEMO finds any constant fraction of the Pareto front in time \(O(n^2)\), improving over the previous estimate of \(O(n^2 \log n)\) for the time to find the first Pareto optimum. Our methods extend to other classic benchmarks and yield, e.g., the first \(\Omega(n^{k+1})\) lower bound for the OJZJ benchmark in the case that the gap parameter is \(k \in \{2,3\}\). We are therefore optimistic that our new methods will be useful in future mathematical analyses of MOEAs.}, author = {Doerr, Benjamin and Krejca, Martin S. and Opris, Andre}, booktitle = {International Joint Conferences on Artifical Intelligence (IJCAI)}, keywords = {ijcai andreopris martinskrejca benjamindoerr year2025 solelyextern}, pages = {8876-8884}, title = {Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm}, year = 2025 }

Krogmann, Simon; Lenzner, Pascal; Skopalik, Alexander; Sträubig, Tobias Social Welfare in Battery Charging GamesSymposium on Algorithmic Game Theory (SAGT) 2025
[ BibTeX ] [ Download ]
 
@inproceedings{krogmann2025social, author = {Krogmann, Simon and Lenzner, Pascal and Skopalik, Alexander and Sträubig, Tobias}, booktitle = {Symposium on Algorithmic Game Theory (SAGT)}, keywords = {year2025 simonkrogmann pascallenzner alexanderskopalik sagt}, title = {Social Welfare in Battery Charging Games}, year = 2025 }

Agrawal, Akanksha; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Verma, Shaily {Parameterized Saga of First-Fit and Last-Fit Coloring}42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) 2025: 5:1–5:21
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The classic greedy coloring algorithm considers the vertices of an input graph G in a given order and assigns the first available color to each vertex v in G. In the Grundy Coloring problem, the task is to find an ordering of the vertices that will force the greedy algorithm to use as many colors as possible. In the Partial Grundy Coloring, the task is also to color the graph using as many colors as possible. This time, however, we may select both the ordering in which the vertices are considered and which color to assign the vertex. The only constraint is that the color assigned to a vertex v is a color previously used for another vertex if such a color is available. Whether Grundy Coloring and Partial Grundy Coloring admit fixed-parameter tractable (FPT) algorithms, algorithms with running time f(k)n^O(1), where k is the number of colors, was posed as an open problem by Zaker and by Effantin et al., respectively. Recently, Aboulker et al. (STACS 2020 and Algorithmica 2022) resolved the question for Grundy Coloring in the negative by showing that the problem is W[1]-hard. For Partial Grundy Coloring, they obtain an FPT algorithm on graphs that do not contain K_{i,j} as a subgraph (a.k.a. K_{i,j}-free graphs). Aboulker et al. re-iterate the question of whether there exists an FPT algorithm for Partial Grundy Coloring on general graphs and also asks whether Grundy Coloring admits an FPT algorithm on K_{i,j}-free graphs. We give FPT algorithms for Partial Grundy Coloring on general graphs and for Grundy Coloring on K_{i,j}-free graphs, resolving both the questions in the affirmative. We believe that our new structural theorems for partial Grundy coloring and "representative-family" like sets for K_{i,j}-free graphs that we use in obtaining our results may have wider algorithmic applications.
@inproceedings{agrawal_et_al:LIPIcs.STACS.2025.5, abstract = {The classic greedy coloring algorithm considers the vertices of an input graph G in a given order and assigns the first available color to each vertex v in G. In the Grundy Coloring problem, the task is to find an ordering of the vertices that will force the greedy algorithm to use as many colors as possible. In the Partial Grundy Coloring, the task is also to color the graph using as many colors as possible. This time, however, we may select both the ordering in which the vertices are considered and which color to assign the vertex. The only constraint is that the color assigned to a vertex v is a color previously used for another vertex if such a color is available. Whether Grundy Coloring and Partial Grundy Coloring admit fixed-parameter tractable (FPT) algorithms, algorithms with running time f(k)n^O(1), where k is the number of colors, was posed as an open problem by Zaker and by Effantin et al., respectively. Recently, Aboulker et al. (STACS 2020 and Algorithmica 2022) resolved the question for Grundy Coloring in the negative by showing that the problem is W[1]-hard. For Partial Grundy Coloring, they obtain an FPT algorithm on graphs that do not contain K_{i,j} as a subgraph (a.k.a. K_{i,j}-free graphs). Aboulker et al. re-iterate the question of whether there exists an FPT algorithm for Partial Grundy Coloring on general graphs and also asks whether Grundy Coloring admits an FPT algorithm on K_{i,j}-free graphs. We give FPT algorithms for Partial Grundy Coloring on general graphs and for Grundy Coloring on K_{i,j}-free graphs, resolving both the questions in the affirmative. We believe that our new structural theorems for partial Grundy coloring and "representative-family" like sets for K_{i,j}-free graphs that we use in obtaining our results may have wider algorithmic applications.}, address = {Dagstuhl, Germany}, annote = {Keywords: Grundy Coloring, Partial Grundy Coloring, FPT Algorithm, K\underline\{i,j\}-free graphs}, author = {Agrawal, Akanksha and Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket and Verma, Shaily}, booktitle = {42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)}, editor = {Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\ {ê}n Kim}, keywords = {stacs shailyverma}, pages = {5:1–5:21}, publisher = {Schloss Dagstuhl – Leibniz-Zentrum f{ü}r Informatik}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, title = {{Parameterized Saga of First-Fit and Last-Fit Coloring}}, volume = 327, year = 2025 }

Casteigts, Arnaud; Döring, Michelle; Morawietz, Nils Realization of Temporally Connected Graphs Based on Degree Sequencesto appear at ISAAC 2025
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Given an undirected graph G, the problem of deciding whether G admits a simple and proper time-labeling that makes it temporally connected is known to be NP-hard (Göbel et al., 1991). In this article, we relax this problem and ask whether a given degree sequence can be realized as a temporally connected graph. Our main results are a complete characterization of the feasible cases, and a recognition algorithm that runs in O(n) time for graphical degree sequences (realized as simple temporal graphs) and in O(n+m) time for multigraphical degree sequences (realized as non-simple temporal graphs, where the number of time labels on an edge corresponds to the multiplicity of the edge in the multigraph). In fact, these algorithms can be made constructive at essentially no cost. Namely, we give a constructive O(n+m) time algorithm that outputs, for a given (multi)graphical degree sequence \mathbf{d}, a temporally connected graph whose underlying (multi)graph is a realization of \mathbf{d}, if one exists.
@inproceedings{casteigts_RealizationTemporally_2025, abstract = {Given an undirected graph G, the problem of deciding whether G admits a simple and proper time-labeling that makes it temporally connected is known to be NP-hard (Göbel et al., 1991). In this article, we relax this problem and ask whether a given degree sequence can be realized as a temporally connected graph. Our main results are a complete characterization of the feasible cases, and a recognition algorithm that runs in O(n) time for graphical degree sequences (realized as simple temporal graphs) and in O(n+m) time for multigraphical degree sequences (realized as non-simple temporal graphs, where the number of time labels on an edge corresponds to the multiplicity of the edge in the multigraph). In fact, these algorithms can be made constructive at essentially no cost. Namely, we give a constructive O(n+m) time algorithm that outputs, for a given (multi)graphical degree sequence \mathbf{d}, a temporally connected graph whose underlying (multi)graph is a realization of \mathbf{d}, if one exists.}, author = {Casteigts, Arnaud and Döring, Michelle and Morawietz, Nils}, booktitle = {to appear at ISAAC}, keywords = {ISAAC isaac temporalreachability nilsmorawietz temporalgraphs TCrealizable year2025 michelledoering realization arnaudcasteigts degreesequences}, title = {Realization of Temporally Connected Graphs Based on Degree Sequences}, year = 2025 }

Döring, Michelle Simple, Strict, Proper, and Directed: Comparing Reachability in Directed and Undirected Temporal Graphsto appear at ISAAC 2025
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
We present the first comprehensive analysis of temporal settings for directed temporal graphs, fully resolving their hierarchy with respect to support, reachability, and induced-reachability equivalence. These notions, introduced by Casteigts, Corsini, and Sarkar, capture different levels of equivalence between temporal graph classes. Their analysis focused on undirected graphs under three dimensions: strict vs. non-strict (whether times along paths strictly increase), proper vs. arbitrary (whether adjacent edges can appear simultaneously), and simple vs. multi-labeled (whether an edge can appear multiple times). In this work, we extend their framework by adding the fundamental distinction of directed vs. undirected. Our results reveal a single-strand hierarchy for directed graphs, with strict & simple being the most expressive class and proper & simple the least expressive. In contrast, undirected graphs form a two-strand hierarchy, with strict & multi-labeled being the most expressive and proper & simple the least expressive. The two strands are formed by the non-strict & simple and the strict & simple class, which we show to be incomparable. In addition to examining the internal hierarchies of directed and of undirected graph classes, we compare the two. We show that each undirected class can be transformed into its directed counterpart under reachability equivalence, while no directed class can be transformed into any undirected one. Our findings have significant implications for the study of computational problems on temporal graphs. Positive results in more expressive graph classes extend to weaker classes as long as the problem is independent under reachability equivalence. Conversely, hardness results for a less expressive class propagate to stronger classes. We hope these findings will inspire a unified approach for analyzing temporal graphs under the different settings.
@inproceedings{doering_SimpleStrict_2025, abstract = {We present the first comprehensive analysis of temporal settings for directed temporal graphs, fully resolving their hierarchy with respect to support, reachability, and induced-reachability equivalence. These notions, introduced by Casteigts, Corsini, and Sarkar, capture different levels of equivalence between temporal graph classes. Their analysis focused on undirected graphs under three dimensions: strict vs. non-strict (whether times along paths strictly increase), proper vs. arbitrary (whether adjacent edges can appear simultaneously), and simple vs. multi-labeled (whether an edge can appear multiple times). In this work, we extend their framework by adding the fundamental distinction of directed vs. undirected. Our results reveal a single-strand hierarchy for directed graphs, with strict & simple being the most expressive class and proper & simple the least expressive. In contrast, undirected graphs form a two-strand hierarchy, with strict & multi-labeled being the most expressive and proper & simple the least expressive. The two strands are formed by the non-strict & simple and the strict & simple class, which we show to be incomparable. In addition to examining the internal hierarchies of directed and of undirected graph classes, we compare the two. We show that each undirected class can be transformed into its directed counterpart under reachability equivalence, while no directed class can be transformed into any undirected one. Our findings have significant implications for the study of computational problems on temporal graphs. Positive results in more expressive graph classes extend to weaker classes as long as the problem is independent under reachability equivalence. Conversely, hardness results for a less expressive class propagate to stronger classes. We hope these findings will inspire a unified approach for analyzing temporal graphs under the different settings.}, author = {Döring, Michelle}, booktitle = {to appear at ISAAC}, keywords = {isomorphism graphstructure ISAAC expressivity isaac graphclasses temporalgraphs year2025 reachability temporalsettings michelledoering directed}, title = {Simple, Strict, Proper, and Directed: Comparing Reachability in Directed and Undirected Temporal Graphs}, year = 2025 }

2025

Li, Xiaoyue; Kötzing, Timo; Baguley, Samuel Algorithm Performance Comparison of the (1+1) EA with Heavy-Tailed Mutators 2025
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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.
@article{noauthororeditor, abstract = {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.}, author = {Li, Xiaoyue and Kötzing, Timo and Baguley, Samuel}, keywords = {sys:relevantfor:ae xiaoyueli timokoetzing}, title = {Algorithm Performance Comparison of the (1+1) EA with Heavy-Tailed Mutators}, year = 2025 }

Friedrich, Tobias; Kötzing, Timo; Neumann, Aneta; Neumann, Frank; Radhakrishnan, Aishwarya Analysis of the (1+1) EA on LeadingOnes with ConstraintsAlgorithmica 2025
[ BibTeX ] [ DOI ] [ Download ]
 
@article{friedrich2025analysis, author = {Friedrich, Tobias and Kötzing, Timo and Neumann, Aneta and Neumann, Frank and Radhakrishnan, Aishwarya}, editor = {Algorithmica}, journal = {Algorithmica}, keywords = {myown algorithmica sys:relevantfor:ae aishwaryaradhakrishnan timokoetzing tobiasfriedrich frankneumann}, title = {Analysis of the (1+1) EA on LeadingOnes with Constraints}, volume = 2025, year = 2025 }

Baguley, Samuel; Friedrich, Tobias; Neumann, Aneta; Neumann, Frank; Pappik, Marcus; Zeif, Ziena Fixed Parameter Multi-Objective Evolutionary Algorithms for the W-Separator ProblemAlgorithmica 2025: 1432–0541
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
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.
@article{baguley2025fixed, 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.}, author = {Baguley, Samuel and Friedrich, Tobias and Neumann, Aneta and Neumann, Frank and Pappik, Marcus and Zeif, Ziena}, journal = {Algorithmica}, keywords = {anetaneumann algorithmica sys:relevantfor:ae zienazeif marcuspappik samuelbaguley tobiasfriedrich year2025 frankneumann}, pages = {1432-0541}, title = {Fixed Parameter Multi-Objective Evolutionary Algorithms for the W-Separator Problem}, year = 2025 }

Berger, Julian; Friedrich, Tobias; Lenzner, Pascal; Paraskevi, Voula; Ruff, Janosch Strategic Network Creation for Enabling Greedy RoutingConference on Artificial Intelligence (AAAI) 2025
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Today we rely on networks that are created and maintained by smart devices. For such networks, there is no governing central authority but instead the network structure is shaped by the decisions of selfish intelligent agents. A key property of such communication networks is that they should be easy to navigate for routing data. For this, a common approach is greedy routing, where every device simply routes data to a neighbor that is closer to the respective destination. Networks of intelligent agents can be analyzed via a game-theoretic approach and in the last decades many variants of network creation games have been proposed and analyzed. In this paper we present the first game-theoretic network creation model that incorporates greedy routing, i.e., the strategic agents in our model are embedded in some metric space and strive for creating a network among themselves where all-pairs greedy routing is enabled. Besides this, the agents optimize their connection quality within the created network by aiming for greedy routing paths with low stretch. For our model, we analyze the existence of (approximate)-equilibria and the computational hardness in different underlying metric spaces. E.g., we characterize the set of equilibria in 1-2-metrics and tree metrics and show that Nash equilibria always exist. For Euclidean space, the setting which is most relevant in practice, we prove that equilibria are not guaranteed to exist but that the well-known \(\Theta\)-graph construction yields networks having a low stretch that are game-theoretically almost stable. For general metric spaces, we show that approximate equilibria exist where the approximation factor depends on the cost of maintaining any link.
@article{bflmr-aaai25, abstract = {Today we rely on networks that are created and maintained by smart devices. For such networks, there is no governing central authority but instead the network structure is shaped by the decisions of selfish intelligent agents. A key property of such communication networks is that they should be easy to navigate for routing data. For this, a common approach is greedy routing, where every device simply routes data to a neighbor that is closer to the respective destination. Networks of intelligent agents can be analyzed via a game-theoretic approach and in the last decades many variants of network creation games have been proposed and analyzed. In this paper we present the first game-theoretic network creation model that incorporates greedy routing, i.e., the strategic agents in our model are embedded in some metric space and strive for creating a network among themselves where all-pairs greedy routing is enabled. Besides this, the agents optimize their connection quality within the created network by aiming for greedy routing paths with low stretch. For our model, we analyze the existence of (approximate)-equilibria and the computational hardness in different underlying metric spaces. E.g., we characterize the set of equilibria in 1-2-metrics and tree metrics and show that Nash equilibria always exist. For Euclidean space, the setting which is most relevant in practice, we prove that equilibria are not guaranteed to exist but that the well-known \(\Theta\)-graph construction yields networks having a low stretch that are game-theoretically almost stable. For general metric spaces, we show that approximate equilibria exist where the approximation factor depends on the cost of maintaining any link.}, author = {Berger, Julian and Friedrich, Tobias and Lenzner, Pascal and Paraskevi, Voula and Ruff, Janosch}, journal = {Conference on Artificial Intelligence (AAAI)}, keywords = {paraskevimachaira janoschruff julianberger tobiasfriedrich aaai year2025 pascallenzner}, title = {Strategic Network Creation for Enabling Greedy Routing}, year = 2025 }

Friedrich, Tobias; Simonov, Kirill; Soheil, Farehe Binary k-Center with Missing Entries: Structure leads to TractabilityIPEC 2025
[ BibTeX ] [ DOI ]
 
@article{friedrich2026binary, author = {Friedrich, Tobias and Simonov, Kirill and Soheil, Farehe}, journal = {IPEC}, keywords = {myown farehesoheil friedrich}, title = {Binary k-Center with Missing Entries: Structure leads to Tractability}, year = 2025 }

Döring, Michelle; Fehse, Jan; Friedrich, Tobias; Marten, Paula; Mohrin, Niklas; Simonov, Kirill; Soheil, Farehe; Timm, Jakob; Verma, Shaily Parameterized Complexity of Vehicle RoutingIPEC 2025
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
The Vehicle Routing Problem (VRP) is a popular generalization of the Traveling Salesperson Problem. Instead of one salesperson traversing the entire weighted, undirected graph G, there are k vehicles available to jointly cover the set of clients C subseteq V(G). Every vehicle must start at one of the depot vertices D subseteq V(G) and return to its start. Capacitated Vehicle Routing (CVRP) additionally restricts the route of each vehicle by limiting the number of clients it can cover, the distance it can travel, or both. In this work, we study the complexity of VRP and the three variants of CVRP for several parameterizations, in particular focusing on the treewidth of G. We present an FPT algorithm for VRP parameterized by treewidth. For CVRP, we prove paraNP- and W[cdot]-hardness for various parameterizations, including treewidth, thereby rendering the existence of FPT algorithms unlikely. In turn, we provide an XP algorithm for CVRP when parameterized by both treewidth and the vehicle capacity.
@article{döring_ParameterizedVehicleRouting_2025, abstract = {The Vehicle Routing Problem (VRP) is a popular generalization of the Traveling Salesperson Problem. Instead of one salesperson traversing the entire weighted, undirected graph G, there are k vehicles available to jointly cover the set of clients C \subseteq V(G). Every vehicle must start at one of the depot vertices D \subseteq V(G) and return to its start. Capacitated Vehicle Routing (CVRP) additionally restricts the route of each vehicle by limiting the number of clients it can cover, the distance it can travel, or both. In this work, we study the complexity of VRP and the three variants of CVRP for several parameterizations, in particular focusing on the treewidth of G. We present an FPT algorithm for VRP parameterized by treewidth. For CVRP, we prove paraNP- and W[\cdot]-hardness for various parameterizations, including treewidth, thereby rendering the existence of FPT algorithms unlikely. In turn, we provide an XP algorithm for CVRP when parameterized by both treewidth and the vehicle capacity.}, author = {Döring, Michelle and Fehse, Jan and Friedrich, Tobias and Marten, Paula and Mohrin, Niklas and Simonov, Kirill and Soheil, Farehe and Timm, Jakob and Verma, Shaily}, journal = {IPEC}, keywords = {travelingsalesperson niklasmohrin parameterizedcomplexity myown vehiclerouting masterproject kirillsimonov IPEC paulamarten tobiasfriedrich shaileyverma michelledoering ipec janfehse year2025 farehesoheil jakobtimm}, title = {Parameterized Complexity of Vehicle Routing}, year = 2025 }

Filtser, Arnold; Friedrich, Tobias; Issac, Davis; Kumar, Nikhil; Le, Hung; Mallek, Nadym; Zeif, Ziena Optimal Padded Decomposition For Bounded Treewidth GraphsTheoretiCS 2025
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
A \((\beta,\delta,\Delta)\)-padded decomposition of an edge-weighted graph \(G = (V,E,w)\) is a stochastic decomposition into clusters of diameter at most \(\Delta\) such that for every vertex \(v\in V\), the probability that \(\ball_G(v,\gamma\Delta)\) is entirely contained in the cluster containing \(v\) is at least \(e^{-\beta\gamma}\) for every \(\gamma \in [0,\delta]\). Padded decompositions have been studied for decades and have found numerous applications, including metric embedding, multicommodity flow-cut gap, multicut, and zero extension problems, to name a few. In these applications, parameter \(\beta\), called the \emph{padding parameter, is the most important parameter since it decides either the distortion or the approximation ratios. For general graphs with \(n\) vertices, the \emph{padding parameter \(\beta\) is known to be in \(\Theta(\log n)\). Klein, Plotkin, and Rao [KPR93] (KPR) showed that \(K_r\)-minor-free graphs have padding parameter \(beta = \mathcal{O(r^3)\), which is a significant improvement over general graphs when \(r\) is a constant. However, when \(r= \Omega(\log n)\), the padding parameter in KPR decomposition can be much worse than \(\log n\). A long-standing conjecture is that constructing a padded decomposition for \(K_r\)-minor-free graphs is possible with padding parameter \(beta = \mathcal{O(\log r)\). Despite decades of research, the best-known result is \(beta = \mathcal{O(r)\), even for graphs with treewidth at most \(r\). In this work, we make significant progress toward the aforementioned conjecture by showing that graphs with treewidth \(\tw\) admit a padded decomposition with padding parameter \(\mathcal{O(\log \tw)\), which is tight. Our padding parameter is strictly better than \(\mathcal{O(\log n)\) whenever \(tw = n^o(1)}\), and is never worse than what is known for general graphs. As corollaries, we obtain an exponential improvement in dependency on treewidth in a host of algorithmic applications: \(\mathcal{O(\sqrt{ log n cdot \log(\tw)})\) flow-cut gap, the maxflow-min multicut ratio of \(\mathcal{O(\log(\tw))\), an \(\mathcal{O(\log(\tw))\) approximation for the 0-extension problem, an \(\ell^{\mathcal{O(\log n)}_\infty\) embedding with distortion \(\mathcal{O(\log \tw)\), and an \(\mathcal{O(\log \tw)\) bound for integrality gap for the uniform sparsest cut.
@article{filtser2025optimal, abstract = {A \((\beta,\delta,\Delta)\)-padded decomposition of an edge-weighted graph \(G = (V,E,w)\) is a stochastic decomposition into clusters of diameter at most \(\Delta\) such that for every vertex \(v\in V\), the probability that \(\ball_G(v,\gamma\Delta)\) is entirely contained in the cluster containing \(v\) is at least \(e^{-\beta\gamma}\) for every \(\gamma \in [0,\delta]\). Padded decompositions have been studied for decades and have found numerous applications, including metric embedding, multicommodity flow-cut gap, multicut, and zero extension problems, to name a few. In these applications, parameter \(\beta\), called the \emph{padding parameter}, is the most important parameter since it decides either the distortion or the approximation ratios. For general graphs with \(n\) vertices, the \emph{padding parameter} \(\beta\) is known to be in \(\Theta(\log n)\). Klein, Plotkin, and Rao [KPR93] (KPR) showed that \(K_r\)-minor-free graphs have padding parameter \(\beta = \mathcal{O}(r^3)\), which is a significant improvement over general graphs when \(r\) is a constant. However, when \(r= \Omega(\log n)\), the padding parameter in KPR decomposition can be much worse than \(\log n\). A long-standing conjecture is that constructing a padded decomposition for \(K_r\)-minor-free graphs is possible with padding parameter \(\beta = \mathcal{O}(\log r)\). Despite decades of research, the best-known result is \(\beta = \mathcal{O}(r)\), even for graphs with treewidth at most \(r\). In this work, we make significant progress toward the aforementioned conjecture by showing that graphs with treewidth \(\tw\) admit a padded decomposition with padding parameter \(\mathcal{O}(\log \tw)\), which is tight. Our padding parameter is strictly better than \(\mathcal{O}(\log n)\) whenever \(\tw = n^{o(1)}\), and is never worse than what is known for general graphs. As corollaries, we obtain an exponential improvement in dependency on treewidth in a host of algorithmic applications: \(\mathcal{O}(\sqrt{ \log n \cdot \log(\tw)})\) flow-cut gap, the maxflow-min multicut ratio of \(\mathcal{O}(\log(\tw))\), an \(\mathcal{O}(\log(\tw))\) approximation for the 0-extension problem, an \(\ell^{\mathcal{O}(\log n)}_\infty\) embedding with distortion \(\mathcal{O}(\log \tw)\), and an \(\mathcal{O}(\log \tw)\) bound for integrality gap for the uniform sparsest cut.}, author = {Filtser, Arnold and Friedrich, Tobias and Issac, Davis and Kumar, Nikhil and Le, Hung and Mallek, Nadym and Zeif, Ziena}, journal = {TheoretiCS}, keywords = {sys:relevantfor:ae zienazeif nikhilkumar davisissac theoretics tobiasfriedrich year2025 nadymmallek}, title = {Optimal Padded Decomposition For Bounded Treewidth Graphs}, year = 2025 }

Baguley, Samuel; Maus, Yannic Maus; Ruff, Janosch; Skretas, George Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for ColouringInternational Symposium on Theoretical Aspects of Computer Science (STACS) 2025: 13:1–13:20
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
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/\sqrt{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.
@conference{bmrs-stacs25, abstract = {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/\sqrt{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.}, author = {Baguley, Samuel and Maus, Yannic Maus and Ruff, Janosch and Skretas, George}, booktitle = {International Symposium on Theoretical Aspects of Computer Science (STACS)}, keywords = {samuelbaguley stacs janoschruff year2025 georgeskretas}, pages = {13:1-13:20}, title = {Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for Colouring}, year = 2025 }

Deligkas, Argyrios; Döring, Michelle; Eiben, Eduard; Goldsmith, Tiger-Lily; Skretas, George; Tennigkeit, Georg How Many Lines to Paint the City: Exact Edge-Cover in Temporal GraphsProceedings of the AAAI Conference on Artificial Intelligence 2025: 26498–26506
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Logistics and transportation networks require a large amount of resources to realise necessary connections between locations and minimizing these resources is a vital aspect of planning research. Since such networks have dynamic connections that are only available at specific times, intricate models are needed to portray them accurately. In this paper, we study the problem of minimizing the number of resources needed to realise a dynamic network, using the temporal graphs model. In a temporal graph, edges appear at specific points in time. Given a temporal graph and a natural number k, we ask whether we can cover every temporal edge exactly once using at most k temporal journeys; in a temporal journey consecutive edges have to adhere to the order of time. We conduct a thorough investigation of the complexity of the problem with respect to four dimensions: (a) whether the type of the temporal journey is a walk, a trail, or a path; (b) whether the chronological order of edges in the journey is strict or non-strict; (c) whether the temporal graph is directed or undirected; (d) whether the start and end points of each journey are given. We almost completely resolve the complexity of these problems and provide dichotomies for each of them with respect to k.
@inproceedings{deligkas_HowMany_2025, abstract = {Logistics and transportation networks require a large amount of resources to realise necessary connections between locations and minimizing these resources is a vital aspect of planning research. Since such networks have dynamic connections that are only available at specific times, intricate models are needed to portray them accurately. In this paper, we study the problem of minimizing the number of resources needed to realise a dynamic network, using the temporal graphs model. In a temporal graph, edges appear at specific points in time. Given a temporal graph and a natural number k, we ask whether we can cover every temporal edge exactly once using at most k temporal journeys; in a temporal journey consecutive edges have to adhere to the order of time. We conduct a thorough investigation of the complexity of the problem with respect to four dimensions: (a) whether the type of the temporal journey is a walk, a trail, or a path; (b) whether the chronological order of edges in the journey is strict or non-strict; (c) whether the temporal graph is directed or undirected; (d) whether the start and end points of each journey are given. We almost completely resolve the complexity of these problems and provide dichotomies for each of them with respect to k.}, author = {Deligkas, Argyrios and Döring, Michelle and Eiben, Eduard and Goldsmith, Tiger-Lily and Skretas, George and Tennigkeit, Georg}, journal = {Proceedings of the AAAI Conference on Artificial Intelligence}, keywords = {argyriosdeligkas tigerlilygoldsmith parameterizedcomplexity pathcover eduardeiben aaai michelledoering georgtennigkeit temporalpathgraph exactedge-cover temporalpathumber temporalgraphs year2025 reachability georgeskretas}, month = {Apr.}, number = 25, pages = {26498-26506}, title = {How Many Lines to Paint the City: Exact Edge-Cover in Temporal Graphs}, volume = 39, year = 2025 }

Krogmann, Simon; Lenzner, Pascal; Skopalik, Alexander The Bakers and Millers Game with Restricted LocationsAutonomous Agents and Multiagent Systems (AAMAS) 2025
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
We study strategic location choice by customers and sellers, termed the Bakers and Millers Game in the literature. In our generalized setting, each miller can freely choose any location for setting up a mill, while each baker is restricted in the choice of location for setting up a bakery. For optimal bargaining power, a baker would like to select a location with many millers to buy flour from and with little competition from other bakers. Likewise, a miller aims for a location with many bakers and few competing millers. Thus, both types of agents choose locations to optimize the ratio of agents of opposite type divided by agents of the same type at their chosen location. Originally raised in the context of Fractional Hedonic Games, the Bakers and Millers Game has applications that range from commerce to product design. We study the impact of location restrictions on the properties of the game. While pure Nash equilibria trivially exist in the setting without location restrictions, we show via a sophisticated, efficient algorithm that even the more challenging restricted setting admits equilibria. Moreover, the computed equilibrium approximates the optimal social welfare by a factor of at most \(2\left(\frac{e}{e-1}\right)\). Furthermore, we give tight bounds on the price of anarchy/stability. On the conceptual side, the location choice feature adds a new layer to Hedonic Games, in the sense that agents that select the same location form a coalition. This allows to naturally restrict the possible coalitions that can be formed. With this, our model generalizes simple symmetric Fractional Hedonic Games on complete bipartite valuation graphs and also Hedonic Diversity Games with utilities single-peaked at 0. We believe that this generalization is also a very interesting direction for other types of Hedonic Games.
@inproceedings{krogmann2025bakers, abstract = {We study strategic location choice by customers and sellers, termed the Bakers and Millers Game in the literature. In our generalized setting, each miller can freely choose any location for setting up a mill, while each baker is restricted in the choice of location for setting up a bakery. For optimal bargaining power, a baker would like to select a location with many millers to buy flour from and with little competition from other bakers. Likewise, a miller aims for a location with many bakers and few competing millers. Thus, both types of agents choose locations to optimize the ratio of agents of opposite type divided by agents of the same type at their chosen location. Originally raised in the context of Fractional Hedonic Games, the Bakers and Millers Game has applications that range from commerce to product design. We study the impact of location restrictions on the properties of the game. While pure Nash equilibria trivially exist in the setting without location restrictions, we show via a sophisticated, efficient algorithm that even the more challenging restricted setting admits equilibria. Moreover, the computed equilibrium approximates the optimal social welfare by a factor of at most \(2\left(\frac{e}{e-1}\right)\). Furthermore, we give tight bounds on the price of anarchy/stability. On the conceptual side, the location choice feature adds a new layer to Hedonic Games, in the sense that agents that select the same location form a coalition. This allows to naturally restrict the possible coalitions that can be formed. With this, our model generalizes simple symmetric Fractional Hedonic Games on complete bipartite valuation graphs and also Hedonic Diversity Games with utilities single-peaked at 0. We believe that this generalization is also a very interesting direction for other types of Hedonic Games.}, author = {Krogmann, Simon and Lenzner, Pascal and Skopalik, Alexander}, booktitle = {Autonomous Agents and Multiagent Systems (AAMAS)}, keywords = {year2025 aamas simonkrogmann pascallenzner alexanderskopalik}, title = {The Bakers and Millers Game with Restricted Locations}, year = 2025 }

Niklanovits, Aikaterini; Simonov, Kirill; Verma, Shaily; Zeif, Ziena Connected Partitions via Connected Dominating SetsEuropean Symposium on Algorithms (ESA) 2025
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The classical theorem due to GyHo}ri and Lovász states that any \(k\)-connected graph \(G\) admits a partition into \(k\) connected subgraphs, where each subgraph has a prescribed size and contains a prescribed vertex, as long as the total size of target subgraphs is equal to the size of \(G\). However, this result is notoriously evasive in terms of efficient constructions, and it is still unknown whether such a partition can be computed in polynomial time, even for \(k = 5\). We make progress towards an efficient constructive version of the GyHo}ri--Lovász theorem by considering a natural strengthening of the \(k\)-connectivity requirement. Specifically, we show that the desired connected partition can be found in polynomial time, if \(G\) contains\(k\) disjoint connected dominating sets. As a consequence of this result, we give several efficient approximate and exact constructive versions of the original GyHo}ri--Lovász theorem: \begin{itemize item On general graphs, a GyHo}ri--Lovász partition with \(k\) parts can be computed in polynomial time when the input graph has connectivity \(\Omega(k \cdot \log^2 n)\); item On convex bipartite graphs, connectivity of \(4k\) is sufficient; item On biconvex graphs and interval graphs, connectivity of \(k\) is sufficient, meaning that our algorithm gives a ``true'' constructive version of the theorem on these graph classes. \end{itemize
@inproceedings{DBLP:journals/corr/abs-2503-13112, abstract = {The classical theorem due to Gy\H{o}ri and Lov{á}sz states that any \(k\)-connected graph \(G\) admits a partition into \(k\) connected subgraphs, where each subgraph has a prescribed size and contains a prescribed vertex, as long as the total size of target subgraphs is equal to the size of \(G\). However, this result is notoriously evasive in terms of efficient constructions, and it is still unknown whether such a partition can be computed in polynomial time, even for \(k = 5\). We make progress towards an efficient constructive version of the Gy\H{o}ri–Lov{á}sz theorem by considering a natural strengthening of the \(k\)-connectivity requirement. Specifically, we show that the desired connected partition can be found in polynomial time, if \(G\) contains\(k\) disjoint connected dominating sets. As a consequence of this result, we give several efficient approximate and exact constructive versions of the original Gy\H{o}ri–Lov{á}sz theorem: \begin{itemize} \item On general graphs, a Gy\H{o}ri–Lov{á}sz partition with \(k\) parts can be computed in polynomial time when the input graph has connectivity \(\Omega(k \cdot \log^2 n)\); \item On convex bipartite graphs, connectivity of \(4k\) is sufficient; \item On biconvex graphs and interval graphs, connectivity of \(k\) is sufficient, meaning that our algorithm gives a ``true'' constructive version of the theorem on these graph classes. \end{itemize}}, author = {Niklanovits, Aikaterini and Simonov, Kirill and Verma, Shaily and Zeif, Ziena}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {sys:relevantfor:ae zienazeif esa kirillsimonov aikaterininiklanovits shailyverma year2025}, title = {Connected Partitions via Connected Dominating Sets}, year = 2025 }

Aivasiliotis, Panagiotis; Göbel, Andreas; Roth, Marc; Schmitt, Johannes Parameterised Holant Problems52nd International Colloquium on Automata, Languages, and Programming (ICALP) 2025: 7:1–7:14
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We investigate the complexity of parameterised holant problems p-Holant(S) for families of symmetric signatures S. The parameterised holant framework has been introduced by Curticapean in 2015 as a counter-part to the classical and well-established theory of holographic reductions and algorithms, and it constitutes an extensive family of coloured and weighted counting constraint satisfaction problems on graph-like structures, encoding as special cases various well-studied counting problems in parameterised and fine-grained complexity theory such as counting edge-colourful k-matchings, graph-factors, Eulerian orientations or, more generally, subgraphs with weighted degree constraints. We establish an exhaustive complexity trichotomy along the set of signatures S: Depending on the signatures, p-Holant(S) is either (1) solvable in FPT-near-linear time, i.e., in time f(k)·Õ(|x|), or (2) solvable in “FPT-matrix-multiplication time”, i.e., in time f(k)·O(n^ω), where n is the number of vertices of the underlying graph, but not solvable in FPT-near-linear time, unless the Triangle Conjecture fails, or (3) #W[1]-complete and no significant improvement over the naive brute force algorithm is possible unless the Exponential Time Hypothesis fails. This classification reveals a significant and surprising gap in the complexity landscape of parameterised Holants: Not only is every instance either fixed-parameter tractable or #W[1]-complete, but additionally, every FPT instance is solvable in time (at most) f(k)·O(n^ω). We show that there are infinitely many instances of each of the types; for example, all constant signatures yield holant problems of type (1), and the problem of counting edge-colourful k-matchings modulo p is of type (p) for p ∈ 2,3. Finally, we also establish a complete classification for a natural uncoloured version of parameterised holant problem p-UnColHolant(S), which encodes as special cases the non-coloured analogues of the aforementioned examples. We show that the complexity of p-UnColHolant(S) is different: Depending on S all instances are either solvable in FPT-near-linear time, or #W[1]-complete, that is, there are no instances of type (2).
@inproceedings{aivasiliotis2025parameterised, abstract = {We investigate the complexity of parameterised holant problems p-Holant(S) for families of symmetric signatures S. The parameterised holant framework has been introduced by Curticapean in 2015 as a counter-part to the classical and well-established theory of holographic reductions and algorithms, and it constitutes an extensive family of coloured and weighted counting constraint satisfaction problems on graph-like structures, encoding as special cases various well-studied counting problems in parameterised and fine-grained complexity theory such as counting edge-colourful k-matchings, graph-factors, Eulerian orientations or, more generally, subgraphs with weighted degree constraints. We establish an exhaustive complexity trichotomy along the set of signatures S: Depending on the signatures, p-Holant(S) is either (1) solvable in FPT-near-linear time, i.e., in time f(k)·Õ(|x|), or (2) solvable in “FPT-matrix-multiplication time”, i.e., in time f(k)·O(n^ω), where n is the number of vertices of the underlying graph, but not solvable in FPT-near-linear time, unless the Triangle Conjecture fails, or (3) #W[1]-complete and no significant improvement over the naive brute force algorithm is possible unless the Exponential Time Hypothesis fails. This classification reveals a significant and surprising gap in the complexity landscape of parameterised Holants: Not only is every instance either fixed-parameter tractable or #W[1]-complete, but additionally, every FPT instance is solvable in time (at most) f(k)·O(n^ω). We show that there are infinitely many instances of each of the types; for example, all constant signatures yield holant problems of type (1), and the problem of counting edge-colourful k-matchings modulo p is of type (p) for p ∈ {2,3}. Finally, we also establish a complete classification for a natural uncoloured version of parameterised holant problem p-UnColHolant(S), which encodes as special cases the non-coloured analogues of the aforementioned examples. We show that the complexity of p-UnColHolant(S) is different: Depending on S all instances are either solvable in FPT-near-linear time, or #W[1]-complete, that is, there are no instances of type (2).}, author = {Aivasiliotis, Panagiotis and Göbel, Andreas and Roth, Marc and Schmitt, Johannes}, booktitle = {52nd International Colloquium on Automata, Languages, and Programming (ICALP)}, keywords = {myown sys:relevantfor:ae panagiotisaivasiliotis friedrich}, pages = {7:1–7:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, title = {Parameterised Holant Problems}, volume = 334, year = 2025 }

Agrawal, Akanksha; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Verma, Shaily Parameterized Saga of First-Fit and Last-Fit Coloring42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) 2025: 5:1–5:21
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The classic greedy coloring algorithm considers the vertices of an input graph G in a given order and assigns the first available color to each vertex v in G. In the Grundy Coloring problem, the task is to find an ordering of the vertices that will force the greedy algorithm to use as many colors as possible. In the Partial Grundy Coloring, the task is also to color the graph using as many colors as possible. This time, however, we may select both the ordering in which the vertices are considered and which color to assign the vertex. The only constraint is that the color assigned to a vertex v is a color previously used for another vertex if such a color is available. Whether Grundy Coloring and Partial Grundy Coloring admit fixed-parameter tractable (FPT) algorithms, algorithms with running time f(k)n^O(1), where k is the number of colors, was posed as an open problem by Zaker and by Effantin et al., respectively. Recently, Aboulker et al. (STACS 2020 and Algorithmica 2022) resolved the question for Grundy Coloring in the negative by showing that the problem is W[1]-hard. For Partial Grundy Coloring, they obtain an FPT algorithm on graphs that do not contain K_i,j as a subgraph (a.k.a. K_i,j-free graphs). Aboulker et al. re-iterate the question of whether there exists an FPT algorithm for Partial Grundy Coloring on general graphs and also asks whether Grundy Coloring admits an FPT algorithm on K_i,j-free graphs. We give FPT algorithms for Partial Grundy Coloring on general graphs and for Grundy Coloring on K_i,j-free graphs, resolving both the questions in the affirmative. We believe that our new structural theorems for partial Grundy coloring and "representative-family" like sets for K_i,j-free graphs that we use in obtaining our results may have wider algorithmic applications.
@inproceedings{agrawal_et_al:LIPIcs.STACS.2025.5, abstract = {The classic greedy coloring algorithm considers the vertices of an input graph G in a given order and assigns the first available color to each vertex v in G. In the Grundy Coloring problem, the task is to find an ordering of the vertices that will force the greedy algorithm to use as many colors as possible. In the Partial Grundy Coloring, the task is also to color the graph using as many colors as possible. This time, however, we may select both the ordering in which the vertices are considered and which color to assign the vertex. The only constraint is that the color assigned to a vertex v is a color previously used for another vertex if such a color is available. Whether Grundy Coloring and Partial Grundy Coloring admit fixed-parameter tractable (FPT) algorithms, algorithms with running time f(k)n^O(1), where k is the number of colors, was posed as an open problem by Zaker and by Effantin et al., respectively. Recently, Aboulker et al. (STACS 2020 and Algorithmica 2022) resolved the question for Grundy Coloring in the negative by showing that the problem is W[1]-hard. For Partial Grundy Coloring, they obtain an FPT algorithm on graphs that do not contain K_{i,j} as a subgraph (a.k.a. K_{i,j}-free graphs). Aboulker et al. re-iterate the question of whether there exists an FPT algorithm for Partial Grundy Coloring on general graphs and also asks whether Grundy Coloring admits an FPT algorithm on K_{i,j}-free graphs. We give FPT algorithms for Partial Grundy Coloring on general graphs and for Grundy Coloring on K_{i,j}-free graphs, resolving both the questions in the affirmative. We believe that our new structural theorems for partial Grundy coloring and "representative-family" like sets for K_{i,j}-free graphs that we use in obtaining our results may have wider algorithmic applications.}, address = {Dagstuhl, Germany}, annote = {Keywords: Grundy Coloring, Partial Grundy Coloring, FPT Algorithm, K\underline\{i,j\}-free graphs}, author = {Agrawal, Akanksha and Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket and Verma, Shaily}, booktitle = {42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)}, editor = {Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\ {ê}n Kim}, keywords = {stacs shailyverma}, pages = {5:1–5:21}, publisher = {Schloss Dagstuhl – Leibniz-Zentrum f{ü}r Informatik}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, title = {{Parameterized Saga of First-Fit and Last-Fit Coloring}}, volume = 327, year = 2025 }

Döring, Michelle Simple, Strict, Proper, and Directed: Comparing Reachability in Directed and Undirected Temporal Graphsto appear at ISAAC 2025
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
We present the first comprehensive analysis of temporal settings for directed temporal graphs, fully resolving their hierarchy with respect to support, reachability, and induced-reachability equivalence. These notions, introduced by Casteigts, Corsini, and Sarkar, capture different levels of equivalence between temporal graph classes. Their analysis focused on undirected graphs under three dimensions: strict vs. non-strict (whether times along paths strictly increase), proper vs. arbitrary (whether adjacent edges can appear simultaneously), and simple vs. multi-labeled (whether an edge can appear multiple times). In this work, we extend their framework by adding the fundamental distinction of directed vs. undirected. Our results reveal a single-strand hierarchy for directed graphs, with strict & simple being the most expressive class and proper & simple the least expressive. In contrast, undirected graphs form a two-strand hierarchy, with strict & multi-labeled being the most expressive and proper & simple the least expressive. The two strands are formed by the non-strict & simple and the strict & simple class, which we show to be incomparable. In addition to examining the internal hierarchies of directed and of undirected graph classes, we compare the two. We show that each undirected class can be transformed into its directed counterpart under reachability equivalence, while no directed class can be transformed into any undirected one. Our findings have significant implications for the study of computational problems on temporal graphs. Positive results in more expressive graph classes extend to weaker classes as long as the problem is independent under reachability equivalence. Conversely, hardness results for a less expressive class propagate to stronger classes. We hope these findings will inspire a unified approach for analyzing temporal graphs under the different settings.
@inproceedings{doering_SimpleStrict_2025, abstract = {We present the first comprehensive analysis of temporal settings for directed temporal graphs, fully resolving their hierarchy with respect to support, reachability, and induced-reachability equivalence. These notions, introduced by Casteigts, Corsini, and Sarkar, capture different levels of equivalence between temporal graph classes. Their analysis focused on undirected graphs under three dimensions: strict vs. non-strict (whether times along paths strictly increase), proper vs. arbitrary (whether adjacent edges can appear simultaneously), and simple vs. multi-labeled (whether an edge can appear multiple times). In this work, we extend their framework by adding the fundamental distinction of directed vs. undirected. Our results reveal a single-strand hierarchy for directed graphs, with strict & simple being the most expressive class and proper & simple the least expressive. In contrast, undirected graphs form a two-strand hierarchy, with strict & multi-labeled being the most expressive and proper & simple the least expressive. The two strands are formed by the non-strict & simple and the strict & simple class, which we show to be incomparable. In addition to examining the internal hierarchies of directed and of undirected graph classes, we compare the two. We show that each undirected class can be transformed into its directed counterpart under reachability equivalence, while no directed class can be transformed into any undirected one. Our findings have significant implications for the study of computational problems on temporal graphs. Positive results in more expressive graph classes extend to weaker classes as long as the problem is independent under reachability equivalence. Conversely, hardness results for a less expressive class propagate to stronger classes. We hope these findings will inspire a unified approach for analyzing temporal graphs under the different settings.}, author = {Döring, Michelle}, booktitle = {to appear at ISAAC}, keywords = {isomorphism graphstructure ISAAC expressivity isaac graphclasses temporalgraphs year2025 reachability temporalsettings michelledoering directed}, title = {Simple, Strict, Proper, and Directed: Comparing Reachability in Directed and Undirected Temporal Graphs}, year = 2025 }

Casteigts, Arnaud; Döring, Michelle; Morawietz, Nils Realization of Temporally Connected Graphs Based on Degree Sequencesto appear at ISAAC 2025
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Given an undirected graph G, the problem of deciding whether G admits a simple and proper time-labeling that makes it temporally connected is known to be NP-hard (Göbel et al., 1991). In this article, we relax this problem and ask whether a given degree sequence can be realized as a temporally connected graph. Our main results are a complete characterization of the feasible cases, and a recognition algorithm that runs in O(n) time for graphical degree sequences (realized as simple temporal graphs) and in O(n+m) time for multigraphical degree sequences (realized as non-simple temporal graphs, where the number of time labels on an edge corresponds to the multiplicity of the edge in the multigraph). In fact, these algorithms can be made constructive at essentially no cost. Namely, we give a constructive O(n+m) time algorithm that outputs, for a given (multi)graphical degree sequence \mathbf{d, a temporally connected graph whose underlying (multi)graph is a realization of \mathbf{d, if one exists.
@inproceedings{casteigts_RealizationTemporally_2025, abstract = {Given an undirected graph G, the problem of deciding whether G admits a simple and proper time-labeling that makes it temporally connected is known to be NP-hard (Göbel et al., 1991). In this article, we relax this problem and ask whether a given degree sequence can be realized as a temporally connected graph. Our main results are a complete characterization of the feasible cases, and a recognition algorithm that runs in O(n) time for graphical degree sequences (realized as simple temporal graphs) and in O(n+m) time for multigraphical degree sequences (realized as non-simple temporal graphs, where the number of time labels on an edge corresponds to the multiplicity of the edge in the multigraph). In fact, these algorithms can be made constructive at essentially no cost. Namely, we give a constructive O(n+m) time algorithm that outputs, for a given (multi)graphical degree sequence \mathbf{d}, a temporally connected graph whose underlying (multi)graph is a realization of \mathbf{d}, if one exists.}, author = {Casteigts, Arnaud and Döring, Michelle and Morawietz, Nils}, booktitle = {to appear at ISAAC}, keywords = {ISAAC isaac temporalreachability nilsmorawietz temporalgraphs TCrealizable year2025 michelledoering realization arnaudcasteigts degreesequences}, title = {Realization of Temporally Connected Graphs Based on Degree Sequences}, year = 2025 }