2026

Doerr, Benjamin; Krejca, Martin S.; Stanković, Milan Improved Runtime Guarantees for the SPEA2 Multi-Objective OptimizerAnnual AAAI Conference on Artificial Intelligence (AAAI) 2026: 36855–36863
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Together with the NSGA-II, the SPEA2 is one of the most widely used domination-based multi-objective evolutionary algorithms. For both algorithms, the known runtime guarantees are linear in the population size; for the NSGA-II, matching lower bounds exist. With a careful study of the more complex selection mechanism of the SPEA2, we show that it has very different population dynamics. From these, we prove runtime guarantees for the OneMinMax, LeadingOnesTrailingZeros, and OneJumpZeroJump benchmarks that depend less on the population size. For example, we show that the SPEA2 with parent population size \(\mu \ge n - 2k + 3\) and offspring population size \(\lambda\) computes the Pareto front of the OneJumpZeroJump benchmark with gap size~$k$ in an expected number of \(O( (\lambda+\mu)n + n^{k+1})\) function evaluations. This shows that the best runtime guarantee of \(O(n^{k+1})\) is not only achieved for \(\mu = \Theta(n)\) and \(\lambda = O(n)\) but for arbitrary \(\mu, \lambda = O(n^k)\). Thus, choosing suitable parameters – a key challenge in using heuristic algorithms – is much easier for the SPEA2 than the NSGA-II.
@inproceedings{doerr2026improved, abstract = {Together with the NSGA-II, the SPEA2 is one of the most widely used domination-based multi-objective evolutionary algorithms. For both algorithms, the known runtime guarantees are linear in the population size; for the NSGA-II, matching lower bounds exist. With a careful study of the more complex selection mechanism of the SPEA2, we show that it has very different population dynamics. From these, we prove runtime guarantees for the OneMinMax, LeadingOnesTrailingZeros, and OneJumpZeroJump benchmarks that depend less on the population size. For example, we show that the SPEA2 with parent population size \(\mu \ge n - 2k + 3\) and offspring population size \(\lambda\) computes the Pareto front of the OneJumpZeroJump benchmark with gap size $k$ in an expected number of \(O( (\lambda+\mu)n + n^{k+1})\) function evaluations. This shows that the best runtime guarantee of \(O(n^{k+1})\) is not only achieved for \(\mu = \Theta(n)\) and \(\lambda = O(n)\) but for arbitrary \(\mu, \lambda = O(n^k)\). Thus, choosing suitable parameters – a key challenge in using heuristic algorithms – is much easier for the SPEA2 than the NSGA-II.}, author = {Doerr, Benjamin and Krejca, Martin S. and Stanković, Milan}, booktitle = {Annual AAAI Conference on Artificial Intelligence (AAAI)}, keywords = {milanstankovic martinskrejca year2026 aaai benjamindoerr solelyextern}, pages = {36855-36863}, title = {Improved Runtime Guarantees for the SPEA2 Multi-Objective Optimizer}, year = 2026 }

Doerr, Benjamin; Krejca, Martin S.; Wietheger, Simon Speeding Up the NSGA-II via Dynamic Population SizesInternational Joint Conferences on Artifical Intelligence (IJCAI) 2026
[ Abstract ] [ BibTeX ] [ Download ]
 
Multi-objective evolutionary algorithms (MOEAs) are among the most widely and successfully applied optimizers for multi-objective problems. However, to store many optimal trade-offs (the Pareto optima) simultaneously, MOEAs are typically run with a large population of solution candidates. This slows down the algorithm and renders the choice of the population size a crucial design decision. In this work, we aim to overcome these difficulties by proposing the dynamic NSGA-II, a variant of the well-known NSGA-II that starts with a small initial population and doubles it after a user-specified number \(\tau\) of function evaluations, up to a maximum size of \(N_{\max}\). We prove that the dynamic NSGA-II with optimal parameters computes the Pareto front of the OneMinMax benchmark of size \(n\) with high probability in \(O(n \log^2 n)\) function evaluations, which is considerably faster than the \(\Theta(n^2 \log n)\) runtime of the static NSGA-II with optimal parameters. For the OneJumpZeroJump benchmark with gap size \(k\), we show a runtime of \(O(n^k \log^2 n)\), improving upon the known runtime of \(\Theta(n^{k+1})\). We also propose a variant that uses the initial population size for a longer period and achieves slightly better performance. Finally, we show that a simple concurrent-run strategy turns our dynamic NSGA-II variants into parameter-less algorithms that exceed the above runtimes only by a logarithmic factor and hence still outperform the static NSGA-II by a factor of \(\tilde\Omega(n)\).
@inproceedings{doerr2026speeding, abstract = {Multi-objective evolutionary algorithms (MOEAs) are among the most widely and successfully applied optimizers for multi-objective problems. However, to store many optimal trade-offs (the Pareto optima) simultaneously, MOEAs are typically run with a large population of solution candidates. This slows down the algorithm and renders the choice of the population size a crucial design decision. In this work, we aim to overcome these difficulties by proposing the dynamic NSGA-II, a variant of the well-known NSGA-II that starts with a small initial population and doubles it after a user-specified number \(\tau\) of function evaluations, up to a maximum size of \(N_{\max}\). We prove that the dynamic NSGA-II with optimal parameters computes the Pareto front of the OneMinMax benchmark of size \(n\) with high probability in \(O(n \log^2 n)\) function evaluations, which is considerably faster than the \(\Theta(n^2 \log n)\) runtime of the static NSGA-II with optimal parameters. For the OneJumpZeroJump benchmark with gap size \(k\), we show a runtime of \(O(n^k \log^2 n)\), improving upon the known runtime of \(\Theta(n^{k+1})\). We also propose a variant that uses the initial population size for a longer period and achieves slightly better performance. Finally, we show that a simple concurrent-run strategy turns our dynamic NSGA-II variants into parameter-less algorithms that exceed the above runtimes only by a logarithmic factor and hence still outperform the static NSGA-II by a factor of \(\tilde\Omega(n)\).}, author = {Doerr, Benjamin and Krejca, Martin S. and Wietheger, Simon}, booktitle = {International Joint Conferences on Artifical Intelligence (IJCAI)}, keywords = {ijcai martinskrejca simonwietheger year2026 benjamindoerr solelyextern}, title = {Speeding Up the NSGA-II via Dynamic Population Sizes}, year = 2026 }

Mallek, Nadym; Simonov, Kirill Optimal Approximations for the Requirement Cut Problem on Sparse Graph ClassesInternational Conference on Current Trends in Theory and Practice of Computer Science 2026: 547–562
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study the Requirement Cut problem, a generalization of numerous classical graph partitioning problems including Multicut, Multiway Cut, k-Cut, and Steiner Multicut among others. Given a graph with edge costs, terminal groups (S_1, ..., S_g) and integer requirements (r_1,... , r_g); the goal is to compute a minimum-cost edge cut that separates each group S_i into at least r_i connected components. Despite many efforts, the best known approximation for Requirement Cut yields a double-logarithmic O(\log(g).\log(n)) approximation ratio as it relies on embedding general graphs into trees and solving the tree instance. In this paper, we explore two largely unstudied structural parameters in order to obtain single-logarithmic approximation ratios: (1) the number of minimal Steiner trees in the instance, which in particular is upper-bounded by the number of spanning trees of the graphs multiplied by g, and (2) the depth of series-parallel graphs. Specifically, we show that if the number of minimal Steiner trees is polynomial in n, then a simple LP-rounding algorithm yields an O(\log n)-approximation, and if the graph is series-parallel with a constant depth then a refined analysis of a known probabilistic embedding yields a O(depth.\log(g))-approximation on series-parallel graphs of bounded depth. Both results extend the known class of graphs that have a single-logarithmic approximation ratio.
@inproceedings{ms-oaotrcposgc-2026, abstract = {We study the Requirement Cut problem, a generalization of numerous classical graph partitioning problems including Multicut, Multiway Cut, k-Cut, and Steiner Multicut among others. Given a graph with edge costs, terminal groups (S_1, ..., S_g) and integer requirements (r_1,... , r_g); the goal is to compute a minimum-cost edge cut that separates each group S_i into at least r_i connected components. Despite many efforts, the best known approximation for Requirement Cut yields a double-logarithmic O(\log(g).\log(n)) approximation ratio as it relies on embedding general graphs into trees and solving the tree instance. In this paper, we explore two largely unstudied structural parameters in order to obtain single-logarithmic approximation ratios: (1) the number of minimal Steiner trees in the instance, which in particular is upper-bounded by the number of spanning trees of the graphs multiplied by g, and (2) the depth of series-parallel graphs. Specifically, we show that if the number of minimal Steiner trees is polynomial in n, then a simple LP-rounding algorithm yields an O(\log n)-approximation, and if the graph is series-parallel with a constant depth then a refined analysis of a known probabilistic embedding yields a O(depth.\log(g))-approximation on series-parallel graphs of bounded depth. Both results extend the known class of graphs that have a single-logarithmic approximation ratio.}, author = {Mallek, Nadym and Simonov, Kirill}, booktitle = {International Conference on Current Trends in Theory and Practice of Computer Science}, editor = {Kozik, Jakub and Wolff, Alexander}, keywords = {sys:relevantfor:ae kirillsimonov sofsem year2026 nadymmallek}, pages = {547–562}, title = {Optimal Approximations for the Requirement Cut Problem on Sparse Graph Classes}, year = 2026 }

Krejca, Martin S.; Witt, Carsten Runtime Analysis of a Compact Genetic Algorithm on a Truly Multi-valued OneMax FunctionParallel Problem Solving from Nature (PPSN) 2026
[ Abstract ] [ BibTeX ] [ Download ]
 
Recently, the runtime analysis of multi-valued estimation-of-distribution algorithms in the framework of Ben Jedidia et al. (TCS 2024) has made significant advancements. However, almost all existing analyses are limited to multi-valued objective functions that in each dimension only distinguish between two types, also called categories, of values and hence can be treated with similar methods as pseudo-Boolean problems. Only recently, Adak and Witt (GECCO 2025) have presented a first runtime analysis of a multi-valued compact genetic algorithm (cGA) on the multi-valued OneMax function G--OneMax\(\colon \{0,\dots,r-1\}^n \to \N\) defined by G-OneMax\((x_1,\dots,x_n)=\sum_{i=1}^n \bm{x}_i\) and truly depending on all \(r\) categories. We improve their runtime result from \(O\bigl(n r^3 \log^2(n)\log (r)\bigr)\) to \(O\bigl(n r \log^3(n)\log^3(r)\bigr)\), both for an optimal choice of the update strength \(K\). Our result matches, up to polylogarithmic factors, the existing bound for the simpler \(r\)-valued OneMax function depending essentially only on two values and analyzed in several previous works. To show the new bound, we use improved drift theorems for processes with high self-loop probabilities and specifically derived concentration inequalities to analyze how probability mass in the multi-valued cGA moves into successively smaller and smaller intervals of the \(r\)-valued frequency matrix.
@inproceedings{krejca2026runtime, abstract = {Recently, the runtime analysis of multi-valued estimation-of-distribution algorithms in the framework of Ben Jedidia et al. (TCS 2024) has made significant advancements. However, almost all existing analyses are limited to multi-valued objective functions that in each dimension only distinguish between two types, also called categories, of values and hence can be treated with similar methods as pseudo-Boolean problems. Only recently, Adak and Witt (GECCO 2025) have presented a first runtime analysis of a multi-valued compact genetic algorithm (cGA) on the multi-valued OneMax function G–OneMax\(\colon \{0,\dots,r-1\}^n \to \N\) defined by G-OneMax\((x_1,\dots,x_n)=\sum_{i=1}^n \bm{x}_i\) and truly depending on all \(r\) categories. We improve their runtime result from \(O\bigl(n r^3 \log^2(n)\log (r)\bigr)\) to \(O\bigl(n r \log^3(n)\log^3(r)\bigr)\), both for an optimal choice of the update strength \(K\). Our result matches, up to polylogarithmic factors, the existing bound for the simpler \(r\)-valued OneMax function depending essentially only on two values and analyzed in several previous works. To show the new bound, we use improved drift theorems for processes with high self-loop probabilities and specifically derived concentration inequalities to analyze how probability mass in the multi-valued cGA moves into successively smaller and smaller intervals of the \(r\)-valued frequency matrix.}, author = {Krejca, Martin S. and Witt, Carsten}, booktitle = {Parallel Problem Solving from Nature (PPSN)}, keywords = {martinskrejca carstenwitt year2026 solelyextern ppsn}, title = {Runtime Analysis of a Compact Genetic Algorithm on a Truly Multi-valued OneMax Function}, year = 2026 }

Döring, Michelle; Malanowski, Jannes; Neubert, Stefan Cost-Free Neutrality for the River Methodto appear at Proceedings of the 40th Annual AAAI Conference on Artificial Intelligence 2026
[ Abstract ] [ BibTeX ] [ Download ]
 
Recently, the River Method was introduced as novel refinement of the Split Cycle voting rule. The decision-making process of River is closely related to the well established Ranked Pairs Method. Both methods consider a margin graph computed from the voters' preferences and eliminate majority cycles in that graph to choose a winner. As ties can occur in the margin graph, a tiebreaker is required along with the preferences. While such a tiebreaker makes the computation efficient, it compromises the fundamental property of neutrality: the voting rule should not favor alternatives in advance. One way to reintroduce neutrality is to use Parallel-Universe Tiebreaking (PUT), where each alternative is a winner if it wins according to any possible tiebreaker. Unfortunately, computing the winners selected by Ranked Pairs with PUT is NP-complete. Given the similarity of River to Ranked Pairs, one might expect River to suffer from the same complexity. Surprisingly, we show the opposite: We present a polynomial-time algorithm for computing River winners with PUT, highlighting significant structural advantages of River over Ranked Pairs. Our Fused-Universe (FUN) algorithm simulates River for every possible tiebreaking in one pass. From the resulting FUN diagram one can then directly read off both the set of winners and, for each winner, a certificate that explains how this alternative dominates the others.
@inproceedings{doring2026costfree, abstract = {Recently, the River Method was introduced as novel refinement of the Split Cycle voting rule. The decision-making process of River is closely related to the well established Ranked Pairs Method. Both methods consider a margin graph computed from the voters' preferences and eliminate majority cycles in that graph to choose a winner. As ties can occur in the margin graph, a tiebreaker is required along with the preferences. While such a tiebreaker makes the computation efficient, it compromises the fundamental property of neutrality: the voting rule should not favor alternatives in advance. One way to reintroduce neutrality is to use Parallel-Universe Tiebreaking (PUT), where each alternative is a winner if it wins according to any possible tiebreaker. Unfortunately, computing the winners selected by Ranked Pairs with PUT is NP-complete. Given the similarity of River to Ranked Pairs, one might expect River to suffer from the same complexity. Surprisingly, we show the opposite: We present a polynomial-time algorithm for computing River winners with PUT, highlighting significant structural advantages of River over Ranked Pairs. Our Fused-Universe (FUN) algorithm simulates River for every possible tiebreaking in one pass. From the resulting FUN diagram one can then directly read off both the set of winners and, for each winner, a certificate that explains how this alternative dominates the others.}, author = {Döring, Michelle and Malanowski, Jannes and Neubert, Stefan}, booktitle = {to appear at Proceedings of the 40th Annual AAAI Conference on Artificial Intelligence}, keywords = {socialchoicetheory jannesmalanowski year2026 aaai votingmethod river michelledoering socialchoicefunction bachelorthesis stefanneubert}, title = {Cost-Free Neutrality for the River Method}, year = 2026 }

Döring, Michelle; Brill, Markus; Heitzig, Jobst The River Methodto appear at Proceedings of the 40th Annual AAAI Conference on Artificial Intelligence 2026
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
We introduce River, a novel Condorcet-consistent voting method that is based on pairwise majority margins and can be seen as a simplified variation of Tideman's Ranked Pairs method. River is simple to explain, simple to compute even 'by hand', and gives rise to an easy-to-interpret certificate in the form of a directed tree. Like Ranked Pairs and Schulze's Beat Path method, River is a refinement of the Split Cycle method and shares with those many desirable properties, including independence of clones. Unlike the other three methods, River satisfies a strong form of resistance to agenda-manipulation that is known as independence of Pareto-dominated alternatives.
@inproceedings{döring_River_2025, abstract = {We introduce River, a novel Condorcet-consistent voting method that is based on pairwise majority margins and can be seen as a simplified variation of Tideman's Ranked Pairs method. River is simple to explain, simple to compute even 'by hand', and gives rise to an easy-to-interpret certificate in the form of a directed tree. Like Ranked Pairs and Schulze's Beat Path method, River is a refinement of the Split Cycle method and shares with those many desirable properties, including independence of clones. Unlike the other three methods, River satisfies a strong form of resistance to agenda-manipulation that is known as independence of Pareto-dominated alternatives.}, author = {Döring, Michelle and Brill, Markus and Heitzig, Jobst}, booktitle = {to appear at Proceedings of the 40th Annual AAAI Conference on Artificial Intelligence}, keywords = {splitcycle paretodomination socialchoicetheory markusbrill year2026 aaai votingmethod jobstheitzig river michelledoering socialchoicefunction axiomaticanalysis}, title = {The River Method}, year = 2026 }

2026

de la Haye, Merlin; Lenzer, Pascal; Soheil, Farehe; Wunderlich, Marcus Metric Hedonic Games on the LineAAMAS 2026
[ BibTeX ] [ DOI ]
 
@article{delahaye2026metric, author = {de la Haye, Merlin and Lenzer, Pascal and Soheil, Farehe and Wunderlich, Marcus}, journal = {AAMAS}, keywords = {myown farehesoheil friedrich}, title = {Metric Hedonic Games on the Line}, year = 2026 }

Casel, Katrin; Friedrich, Tobias; Niklanovits, Aikaterini; Simonov, Kirill; Zeif, Ziena Combining Crown Structures for Vulnerability MeasuresAlgorithmica 2026
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Over the past decades, various metrics have emerged in graph theory to grasp the complex nature of network vulnerability. In this paper, we study two specific measures: (weighted) vertex integrity (wVI) and (weighted) component order connectivity (wCOC). These measures not only evaluate the number of vertices required to decompose a graph into fragments, but also take into account the size of the largest remaining component. The main focus of our paper is on kernelization algorithms tailored to both measures. We capitalize on the structural attributes inherent in different crown decompositions, strategically combining them to introduce novel kernelization algorithms that advance the current state of the field. In particular, we extend the scope of the balanced crown decomposition provided by Casel et al.~\cite{DBLP:conf/esa/Casel0INZ21 and expand the applicability of crown decomposition techniques. In summary, we improve the vertex kernel of VI from \(p^3\) to \(p^2\), and of wVI from \(p^3\) to \(3(p^2 + p^1.5 p_{\ell})\), where \(p_{\ell} < p\) represents the weight of the heaviest component after removing a solution. For wCOC we improve the vertex kernel from \(\mathcal{O(k^2W + kW^2)\) to \(3\mu(k + \sqrt{\mu}W)\), where \(mu = \max(k,W)\). We also give a combinatorial algorithm that provides a \(2kW\) vertex kernel in fixed-parameter tractable time when parameterized by \(r\), where \(r \leq k\) is the size of a maximum \((W+1)\)-packing. We further show that the algorithm computing the \(2kW\) vertex kernel for COC can be transformed into a polynomial algorithm for two special cases, namely when \(W=1\), which corresponds to the well-known vertex cover problem, and for claw-free graphs. In particular, we show a new way to obtain a \(2k\) vertex kernel (or to obtain a 2-approximation) for the vertex cover problem by only using crown structures.
@article{casel2025combining, abstract = {Over the past decades, various metrics have emerged in graph theory to grasp the complex nature of network vulnerability. In this paper, we study two specific measures: (weighted) vertex integrity (wVI) and (weighted) component order connectivity (wCOC). These measures not only evaluate the number of vertices required to decompose a graph into fragments, but also take into account the size of the largest remaining component. The main focus of our paper is on kernelization algorithms tailored to both measures. We capitalize on the structural attributes inherent in different crown decompositions, strategically combining them to introduce novel kernelization algorithms that advance the current state of the field. In particular, we extend the scope of the balanced crown decomposition provided by Casel et al.&nbsp;\cite{DBLP:conf/esa/Casel0INZ21} and expand the applicability of crown decomposition techniques. In summary, we improve the vertex kernel of VI from \(p^3\) to \(p^2\), and of wVI from \(p^3\) to \(3(p^2 + {p}^{1.5} p_{\ell})\), where \(p_{\ell} < p\) represents the weight of the heaviest component after removing a solution. For wCOC we improve the vertex kernel from \(\mathcal{O}(k^2W + kW^2)\) to \(3\mu(k + \sqrt{\mu}W)\), where \(\mu = \max(k,W)\). We also give a combinatorial algorithm that provides a \(2kW\) vertex kernel in fixed-parameter tractable time when parameterized by \(r\), where \(r \leq k\) is the size of a maximum \((W+1)\)-packing. We further show that the algorithm computing the \(2kW\) vertex kernel for COC can be transformed into a polynomial algorithm for two special cases, namely when \(W=1\), which corresponds to the well-known vertex cover problem, and for claw-free graphs. In particular, we show a new way to obtain a \(2k\) vertex kernel (or to obtain a 2-approximation) for the vertex cover problem by only using crown structures.}, author = {Casel, Katrin and Friedrich, Tobias and Niklanovits, Aikaterini and Simonov, Kirill and Zeif, Ziena}, journal = {Algorithmica}, keywords = {zienazeif katrincasel kirillsimonov aikaterininiklanovits tobiasfriedrich year2025}, title = {Combining Crown Structures for Vulnerability Measures}, year = 2026 }

Simonov, Kirill; Soheil, Farehe; Verma, Shaily Finding Minimum Distance Preservers: A Parameterized Studyarxiv 2026
[ BibTeX ] [ DOI ]
 
@article{simonov2026finding, author = {Simonov, Kirill and Soheil, Farehe and Verma, Shaily}, journal = {arxiv}, keywords = {myown farehesoheil friedrich}, title = {Finding Minimum Distance Preservers: A Parameterized Study}, year = 2026 }

Aivasiliotis, Panagiotis; Göbel, Andreas; Roth, Marc Symmetric Parameterised Holants on Hypergraphs: Towards a  Classification for Parameterised VCSPsInternational Colloquium on Automata, Languages and Programming (ICALP) 2026
[ BibTeX ]
 
@article{aivasiliotis2026symmetric, author = {Aivasiliotis, Panagiotis and Göbel, Andreas and Roth, Marc}, journal = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {myown sys:relevantfor:ae panagiotisaivasiliotis friedrich}, title = {Symmetric Parameterised Holants on Hypergraphs: Towards a  Classification for Parameterised VCSPs}, year = 2026 }