Tobias Friedrich

AAAI Conference 2025 Conference Paper

Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks

• Davide Bilò
• Keerti Choudhary
• Sarel Cohen
• Tobias Friedrich
• Martin Schirneck

We design sensitivity oracles for error-prone networks. For a network problem Π, the data structure preprocesses a network G=(V,E) and sensitivity parameter f such that, for any set F of up to f link or node failures, it can report the solution of Π in G-F. We study three network problems Π. - L-Hop Shortest Path: Given s,t in V, is there a shortest s-t-path in G-F with at most L links? - k-Path: Does G-F contain a simple path with k links? - k-Clique: Does G-F contain a clique of k nodes? Our main technical contribution is a new construction of (L,f)-replacement path coverings ((L,f)-RPC) in the parameter realm where f = o(log L). An (L,f)-RPC is a family G' of subnetworks of G which, for every set F of at most f links, has a subfamily G'_F such that (i) no subnetwork in G'_F contains a link of F and (ii) for each s,t in V, if G-F contains a shortest s-t-path with at most L links, then some subnetwork in G'_F retains at least one such path. Our (L,f)-RPC has almost the same size as the one by Weimann and Yuster (2013) but it improves the time to query G'_F from Õ(f^2 L^f) to Õ(f^(5/2) L^o(1)). It also improves over the size and query time of the (L,f)-RPC by Karthik and Parter (2021) by nearly a factor of L. From this construction, we derive oracles for L-Hop Shortest Path, k-Path, and k-Clique. Notably, our solution for k-Path improves the query time of the one by Bilò for f=o(log k).

AAAI Conference 2025 Conference Paper

Strategic Network Creation for Enabling Greedy Routing

• Julian Berger
• Tobias Friedrich
• Pascal Lenzner
• Paraskevi Machaira
• Janosch Ruff

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 Θ-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.

AAMAS Conference 2025 Conference Paper

Temporal Network Creation Games: The Impact of Non-Locality and Terminals

• Davide Bilò
• Sarel Cohen
• Tobias Friedrich
• Hans Gawendowicz
• Nicolas Klodt
• Pascal Lenzner
• George Skretas

We live in a world full of networks where our economy, our communication, and even our social life crucially depends on them. These networks typically emerge from the interaction of many entities, which is why researchers study agent-based models of network formation. While traditionally static networks with a fixed set of links were considered, a recent stream of works focuses on networks whose behavior may change over time. In particular, Bilò et al. (IJCAI 2023) recently introduced a game-theoretic network formation model that embeds temporal aspects in networks. More precisely, a network is formed by selfish agents corresponding to nodes in a given host network with edges having labels denoting their availability over time. Each agent strategically selects local, i. e. , incident, edges to ensure temporal reachability towards everyone at low cost. In this work we set out to explore the impact of two novel conceptual features: agents are no longer restricted to creating incident edges, called the global setting, and agents might only want to ensure that they can reach a subset of the other nodes, called the terminal model. For both, we study the existence, structure, and quality of equilibrium networks. For the terminal model, we prove that many core properties crucially depend on the number of terminals. We also develop a novel tool that allows translating equilibrium constructions from the non-terminal model to the terminal model. For the global setting, we show the surprising result that equilibria in the global and the local model are incomparable and we establish a high lower bound on the Price of Anarchy of the global setting that matches the upper bound of the local model. This shows the counter-intuitive fact that allowing agents more flexibility in edge creation does not improve the quality of equilibrium networks. This work is licensed under a Creative Commons Attribution International 4. 0 License. Proc. of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025), Y. Vorobeychik, S. Das, A. Nowé (eds.), May 19 – 23, 2025, Detroit, Michigan, USA. © 2025 International Foundation for Autonomous Agents and Multiagent Systems (www. ifaamas. org). Finally, in contrast to Bilò et al. (IJCAI 2023) where the authors restrict the model to single labels per connection, all of our results hold for the restricted case and the generalized case where every edge can have multiple labels.

AAMAS Conference 2024 Conference Paper

From Market Saturation to Social Reinforcement: Understanding the Impact of Non-Linearity in Information Diffusion Models

• Tobias Friedrich
• Andreas Göbel
• Nicolas Klodt
• Martin S. Krejca
• Marcus Pappik

Diffusion of information in networks is at the core of many problems in AI. Common examples include the spread of ideas and rumors as well as marketing campaigns. Typically, information diffuses at a non-linear rate, for example, if markets become saturated or if users of social networks reinforce each other’s opinions. Despite these characteristics, this area has seen little research, compared to the vast amount of results for linear models, which exhibit less complex dynamics. Especially, when considering the possibility of re-infection, no fully rigorous guarantees exist so far. We address this shortcoming by studying a very general nonlinear diffusion model that captures saturation as well as reinforcement. More precisely, we consider a variant of the SIS model in which vertices get infected at a rate that scales polynomially in the number of their infected neighbors, weighted by an infection coefficient 𝜆. We give the first fully rigorous results for thresholds of 𝜆 at which the expected survival time becomes super-polynomial. For cliques we show that when the infection rate scales sub-linearly, the threshold only shifts by a poly-logarithmic factor, compared to the standard SIS model. In contrast, super-linear scaling changes the process considerably and shifts the threshold by a polynomial term. For stars, sub-linear and super-linear scaling behave similar and both shift the threshold by a polynomial factor. Our bounds are almost tight, as they are only apart by at most a poly-logarithmic factor from the lower thresholds, at which the expected survival time is logarithmic.

IJCAI Conference 2024 Conference Paper

Real-World Networks Are Low-Dimensional: Theoretical and Practical Assessment

• Tobias Friedrich
• Andreas Göbel
• Maximilian Katzmann
• Leon Schiller

Recent empirical evidence suggests that real-world networks have very low underlying dimensionality. We provide a theoretical explanation for this phenomenon as well as develop a linear-time algorithm for detecting the underlying dimensionality of such networks. Our theoretical analysis considers geometric inhomogeneous random graphs (GIRGs), a geometric random graph model, which captures a variety of properties observed in real-world networks. These properties include a heterogeneous degree distribution and non-vanishing clustering coefficient, which is the probability that two random neighbors of a vertex are adjacent. Our first result shows that the clustering coefficient of GIRGs scales inverse exponentially with respect to the number of dimensions d, when the latter is at most logarithmic in n, the number of vertices. Hence, for a GIRG to behave like many real-world networks and have a non-vanishing clustering coefficient, it must come from a geometric space of o(log n) dimensions. Our analysis on GIRGs allows us to obtain a linear-time algorithm for determining the dimensionality of a network. Our algorithm bridges the gap between theory and practice, as it comes with a rigorous proof of correctness and yields results comparable to prior empirical approaches, as indicated by our experiments on real-world instances. The efficiency of our algorithm makes it applicable to very large data-sets. We conclude that very low dimensionalities (from 1 to 10) are needed to explain properties of real-world networks.

AAAI Conference 2024 Conference Paper

The Irrelevance of Influencers: Information Diffusion with Re-Activation and Immunity Lasts Exponentially Long on Social Network Models

• Tobias Friedrich
• Andreas Göbel
• Nicolas Klodt
• Martin S. Krejca
• Marcus Pappik

Information diffusion models on networks are at the forefront of AI research. The dynamics of such models typically follow stochastic models from epidemiology, used to model not only infections but various phenomena, including the behavior of computer viruses and viral marketing campaigns. A core question in this setting is how to efficiently detect the most influential vertices in the host graph such that the infection survives the longest. In processes that incorporate re-infection of the vertices, such as the SIS process, theoretical studies identify parameter thresholds where the survival time of the process rapidly transitions from logarithmic to super-polynomial. These results contradict the intuition that the starting configuration is relevant, since the process will always either die out fast or survive almost indefinitely. A shortcoming of these results is that models incorporating short-term immunity (or creative advertisement fatigue) have not been subjected to such a theoretical analysis so far. We reduce this gap in the literature by studying the SIRS process, a more realistic model, which besides re-infection additionally incorporates short-term immunity. On complex network models, we identify parameter regimes for which the process survives exponentially long, and we get a tight threshold for random graphs. Underlying these results is our main technical contribution, showing a threshold behavior for the survival time of the SIRS process on graphs with large expander subgraphs, such as social network models.

TCS Journal 2023 Journal Article

Polymer dynamics via cliques: New conditions for approximations

• Tobias Friedrich
• Andreas Göbel
• Martin S. Krejca
• Marcus Pappik

polymer models are systems of weighted objects, called polymers, equipped with an incompatibility relation. An important quantity associated with such models is the partition function, which is the weighted sum over all sets of compatible polymers. Various approximation problems reduce to approximating the partition function of a polymer model. Central to the existence of such approximation algorithms are weight conditions of the respective polymer model. Such conditions are derived either via complex analysis or via probabilistic arguments. We follow the latter path and establish a new condition—the clique dynamics condition—, which is less restrictive than the ones in the literature. We introduce a new Markov chain where the clique dynamics condition implies rapid mixing by utilizing cliques of incompatible polymers that naturally arise from the translation of algorithmic problems into polymer models. This leads to improved parameter ranges for several approximation algorithms, such as a factor of at least 2 1 / α for the hard-core model on bipartite α-expanders.

AAMAS Conference 2023 Conference Paper

Single-Peaked Jump Schelling Games

• Tobias Friedrich
• Pascal Lenzner
• Louise Molitor
• Lars Seifert

We contribute to the recent endeavor of investigating residential segregation models with realistic agent behavior by studying Jump Schelling Games with agents having a single-peaked utility function. In such games, there are empty nodes in the graph and agents can strategically jump to such nodes to improve their utility.

IJCAI Conference 2023 Conference Paper

Temporal Network Creation Games

• Davide Bilò
• Sarel Cohen
• Tobias Friedrich
• Hans Gawendowicz
• Nicolas Klodt
• Pascal Lenzner
• George Skretas

Most networks are not static objects, but instead they change over time. This observation has sparked rigorous research on temporal graphs within the last years. In temporal graphs, we have a fixed set of nodes and the connections between them are only available at certain time steps. This gives rise to a plethora of algorithmic problems on such graphs, most prominently the problem of finding temporal spanners, i. e. , the computation of subgraphs that guarantee all pairs reachability via temporal paths. To the best of our knowledge, only centralized approaches for the solution of this problem are known. However, many real-world networks are not shaped by a central designer but instead they emerge and evolve by the interaction of many strategic agents. This observation is the driving force of the recent intensive research on game-theoretic network formation models. In this work we bring together these two recent research directions: temporal graphs and game-theoretic network formation. As a first step into this new realm, we focus on a simplified setting where a complete temporal host graph is given and the agents, corresponding to its nodes, selfishly create incident edges to ensure that they can reach all other nodes via temporal paths in the created network. This yields temporal spanners as equilibria of our game. We prove results on the convergence to and the existence of equilibrium networks, on the complexity of finding best agent strategies, and on the quality of the equilibria. By taking these first important steps, we uncover challenging open problems that call for an in-depth exploration of the creation of temporal graphs by strategic agents.

AAMAS Conference 2022 Conference Paper

Pareto Optimal and Popular House Allocation with Lower and Upper Quotas

• Ágnes Cseh
• Tobias Friedrich
• Jannik Peters

In the house allocation problem with lower and upper quotas, we are given a set of applicants and a set of projects. Each applicant has a strictly ordered preference list over the projects she finds acceptable, while the projects are equipped with a lower and an upper quota. A feasible matching assigns the applicants to the projects in such a way that a project is either matched to no applicant or to a number of applicants between its lower and upper quota. In this model we study two classic optimality concepts: Pareto optimality and popularity. We show that finding a popular matching is hard even if the maximum lower quota is 2 and that finding a perfect Pareto optimal matching, verifying Pareto optimality, and verifying popularity are all NP-complete even if the maximum lower quota is 3. We complement the last three negative results by showing that the problems become polynomial-time solvable when the maximum lower quota is 2, thereby answering two open questions of Cechlárová and Fleiner [16]. Finally, we also study the parameterized complexity of all four mentioned problems.

AIJ Journal 2022 Journal Article

Pareto optimization for subset selection with dynamic cost constraints

• Vahid Roostapour
• Aneta Neumann
• Frank Neumann
• Tobias Friedrich

We consider the subset selection problem for function f with constraint bound B that changes over time. Within the area of submodular optimization, various greedy approaches are commonly used. For dynamic environments we observe that the adaptive variants of these greedy approaches are not able to maintain their approximation quality. Investigating the recently introduced POMC Pareto optimization approach, we show that this algorithm efficiently computes a ϕ = ( α f / 2 ) ( 1 − 1 e α f ) -approximation, where α f is the submodularity ratio of f, for each possible constraint bound b ≤ B. Furthermore, we show that POMC is able to adapt its set of solutions quickly in the case that B increases. Our experimental investigations for the influence maximization in social networks show the advantage of POMC over generalized greedy algorithms. We also consider EAMC, a new evolutionary algorithm with polynomial expected time guarantee to maintain ϕ approximation ratio, and NSGA-II with two different population sizes as advanced multi-objective optimization algorithm, to demonstrate their challenges in optimizing the maximum coverage problem. Our empirical analysis shows that, within the same number of evaluations, POMC is able to perform as good as NSGA-II under linear constraint, while EAMC performs significantly worse than all considered algorithms in most cases.

TCS Journal 2022 Journal Article

The complexity of dependency detection and discovery in relational databases

• Thomas Bläsius
• Tobias Friedrich
• Martin Schirneck

Multi-column dependencies in relational databases come associated with two different computational tasks. The detection problem is to decide whether a dependency of a certain type and size holds in a given database, the discovery problem asks to enumerate all valid dependencies of that type. We settle the complexity of both of these problems for unique column combinations (UCCs), functional dependencies (FDs), and inclusion dependencies (INDs). We show that the detection of UCCs and FDs is W[2]-complete when parameterized by the solution size. The discovery of inclusion-wise minimal UCCs is proven to be equivalent under parsimonious reductions to the transversal hypergraph problem of enumerating the minimal hitting sets of a hypergraph. The discovery of FDs is equivalent to the simultaneous enumeration of the hitting sets of multiple input hypergraphs. We further identify the detection of INDs as one of the first natural W[3]-complete problems. The discovery of maximal INDs is shown to be equivalent to enumerating the maximal satisfying assignments of antimonotone, 3-normalized Boolean formulas.

AAAI Conference 2021 Conference Paper

Selfish Creation of Social Networks

• Davide Bilò
• Tobias Friedrich
• Pascal Lenzner
• Stefanie Lowski
• Anna Melnichenko

Understanding real-world networks has been a core research endeavor throughout the last two decades. Network Creation Games are a promising approach for this from a gametheoretic perspective. In these games, selfish agents corresponding to nodes in a network strategically decide which links to form to optimize their centrality. Many versions have been introduced and analyzed, but none of them fits to modeling the evolution of social networks. In real-world social networks, connections are often established by recommendations from common acquaintances or by a chain of such recommendations. Thus establishing and maintaining a contact with a friend of a friend is easier than connecting to complete strangers. This explains the high clustering, i. e. , the abundance of triangles, in real-world social networks. We propose and analyze a network creation model inspired by real-world social networks. Edges are formed in our model via bilateral consent of both endpoints and the cost for establishing and maintaining an edge is proportional to the distance of the endpoints before establishing the connection. We provide results for generic cost functions, which essentially only must be convex functions in the distance of the endpoints without the respective edge. For this broad class of cost functions, we provide many structural properties of equilibrium networks and prove (almost) tight bounds on the diameter, the Price of Anarchy and the Price of Stability. Moreover, as a proof-of-concept we show via experiments that the created equilibrium networks of our model indeed closely mimics real-world social networks. We observe degree distributions that seem to follow a power-law, high clustering, and low diameters. This can be seen as a promising first step towards game-theoretic network creation models that predict networks featuring all core real-world properties.

TCS Journal 2020 Journal Article

Analysis of the (1 + 1) EA on subclasses of linear functions under uniform and linear constraints

• Tobias Friedrich
• Timo Kötzing
• J.A. Gregor Lagodzinski
• Frank Neumann
• Martin Schirneck

Linear functions have gained great attention in the run time analysis of evolutionary computation methods. The corresponding investigations have provided many effective tools for analyzing more complex problems. So far, the runtime analysis of evolutionary algorithms has mainly focused on unconstrained problems, but problems occurring in applications frequently involve constraints. Therefore, there is a strong need to extend the current analyses and used methods for analyzing unconstrained problems to a setting involving constraints. In this paper, we consider the behavior of the classical ( 1 + 1 ) Evolutionary Algorithm on linear functions under linear constraint. We show tight bounds in the case where the constraint is given by the OneMax function and the objective function is given by either the OneMax or the BinVal function. For the general case we present upper and lower bounds.

IJCAI Conference 2020 Conference Paper

Flow-Based Network Creation Games

• Hagen Echzell
• Tobias Friedrich
• Pascal Lenzner
• Anna Melnichenko

Network Creation Games(NCGs) model the creation of decentralized communication networks like the Internet. In such games strategic agents corresponding to network nodes selfishly decide with whom to connect to optimize some objective function. Past research intensively analyzed models where the agents strive for a central position in the network. This models agents optimizing the network for low-latency applications like VoIP. However, with today's abundance of streaming services it is important to ensure that the created network can satisfy the increased bandwidth demand. To the best of our knowledge, this natural problem of the decentralized strategic creation of networks with sufficient bandwidth has not yet been studied. We introduce Flow-Based NCGs where the selfish agents focus on bandwidth instead of latency. In essence, budget-constrained agents create network links to maximize their minimum or average network flow value to all other network nodes. Equivalently, this can also be understood as agents who create links to increase their connectivity and thus also the robustness of the network. For this novel type of NCG we prove that pure Nash equilibria exist, we give a simple algorithm for computing optimal networks, we show that the Price of Stability is 1 and we prove an (almost) tight bound of 2 on the Price of Anarchy. Last but not least, we show that our models do not admit a potential function.

AAAI Conference 2019 Conference Paper

Greedy Maximization of Functions with Bounded Curvature under Partition Matroid Constraints

• Tobias Friedrich
• Andreas Göbel
• Frank Neumann
• Francesco Quinzan
• Ralf Rothenberger

We investigate the performance of a deterministic GREEDY algorithm for the problem of maximizing functions under a partition matroid constraint. We consider non-monotone submodular functions and monotone subadditive functions. Even though constrained maximization problems of monotone submodular functions have been extensively studied, little is known about greedy maximization of non-monotone submodular functions or monotone subadditive functions. We give approximation guarantees for GREEDY on these problems, in terms of the curvature. We find that this simple heuristic yields a strong approximation guarantee on a broad class of functions. We discuss the applicability of our results to three real-world problems: Maximizing the determinant function of a positive semidefinite matrix, and related problems such as the maximum entropy sampling problem, the constrained maximum cut problem on directed graphs, and combinatorial auction games. We conclude that GREEDY is well-suited to approach these problems. Overall, we present evidence to support the idea that, when dealing with constrained maximization problems with bounded curvature, one needs not search for (approximate) monotonicity to get good approximate solutions.

AAAI Conference 2019 Conference Paper

Pareto Optimization for Subset Selection with Dynamic Cost Constraints

• Vahid Roostapour
• Aneta Neumann
• Frank Neumann
• Tobias Friedrich

In this paper, we consider the subset selection problem for function f with constraint bound B which changes over time. We point out that adaptive variants of greedy approaches commonly used in the area of submodular optimization are not able to maintain their approximation quality. Investigating the recently introduced POMC Pareto optimization approach, we show that this algorithm efficiently computes a φ = (αf /2)(1 − 1 e αf )-approximation, where αf is the submodularity ratio of f, for each possible constraint bound b ≤ B. Furthermore, we show that POMC is able to adapt its set of solutions quickly in the case that B increases. Our experimental investigations for the influence maximization in social networks show the advantage of POMC over generalized greedy algorithms.

IJCAI Conference 2019 Conference Paper

Sharpness of the Satisfiability Threshold for Non-Uniform Random k-SAT

• Tobias Friedrich
• Ralf Rothenberger

We study a more general model to generate random instances of Propositional Satisfiability (SAT) with n Boolean variables, m clauses, and exactly k variables per clause. Additionally, our model is given an arbitrary probability distribution (p_1, .. ., p_n) on the variable occurrences. Therefore, we call it non-uniform random k-SAT. The number m of randomly drawn clauses at which random formulas go from asymptotically almost surely (a. a. s. ) satisfiable to a. a. s. unsatisfiable is called the satisfiability threshold. Such a threshold is called sharp if it approaches a step function as n increases. We identify conditions on the variable probability distribution (p_1, .. ., p_n) under which the satisfiability threshold is sharp if its position is already known asymptotically. This result generalizes Friedgut’s sharpness result from uniform to non-uniform random k -SAT and implies sharpness for thresholds of a wide range of random k -SAT models with heterogeneous probability distributions, for example such models where the variable probabilities follow a power-law.

TCS Journal 2019 Journal Article

Unbiasedness of estimation-of-distribution algorithms

• Tobias Friedrich
• Timo Kötzing
• Martin S. Krejca

In the context of black-box optimization, black-box complexity is used for understanding the inherent difficulty of a given optimization problem. Central to our understanding of nature-inspired search heuristics in this context is the notion of unbiasedness. Specialized black-box complexities have been developed in order to better understand the limitations of these heuristics – especially of (population-based) evolutionary algorithms (EAs). In contrast to this, we focus on a model for algorithms explicitly maintaining a probability distribution over the search space: so-called estimation-of-distribution algorithms (EDAs). We consider the recently introduced n-Bernoulli-λ-EDA framework, which subsumes, for example, the commonly known EDAs PBIL, UMDA, λ -MMAS IB, and cGA. We show that an n-Bernoulli-λ-EDA is unbiased if and only if its probability distribution satisfies a certain invariance property under isometric automorphisms of [ 0, 1 ] n. By restricting how an n-Bernoulli-λ-EDA can perform an update, in a way common to many examples, we derive conciser characterizations, which are easy to verify. We demonstrate this by showing that our examples above are all unbiased.

AAAI Conference 2017 Conference Paper

A Generic Bet-and-Run Strategy for Speeding Up Stochastic Local Search

• Tobias Friedrich
• Timo Kštzing
• Markus Wagner

A common strategy for improving optimization algorithms is to restart the algorithm when it is believed to be trapped in an inferior part of the search space. However, while specific restart strategies have been developed for specific problems (and specific algorithms), restarts are typically not regarded as a general tool to speed up an optimization algorithm. In fact, many optimization algorithms do not employ restarts at all. Recently, bet-and-run was introduced in the context of mixed-integer programming, where first a number of short runs with randomized initial conditions is made, and then the most promising run of these is continued. In this article, we consider two classical NP-complete combinatorial optimization problems, traveling salesperson and minimum vertex cover, and study the effectiveness of different bet-and-run strategies. In particular, our restart strategies do not take any problem knowledge into account, nor are tailored to the optimization algorithm. Therefore, they can be used off-the-shelf. We observe that state-of-the-art solvers for these problems can benefit significantly from restarts on standard benchmark instances.

AAAI Conference 2017 Conference Paper

Phase Transitions for Scale-Free SAT Formulas

• Tobias Friedrich
• Anton Krohmer
• Ralf Rothenberger
• Andrew Sutton

Recently, a number of non-uniform random satisfiability models have been proposed that are closer to practical satisfiability problems in some characteristics. In contrast to uniform random Boolean formulas, scale-free formulas have a variable occurrence distribution that follows a power law. It has been conjectured that such a distribution is a more accurate model for some industrial instances than the uniform random model. Though it seems that there is already an awareness of a threshold phenomenon in such models, there is still a complete picture lacking. In contrast to the uniform model, the critical density threshold does not lie at a single point, but instead exhibits a functional dependency on the power-law exponent. For scale-free formulas with clauses of length k = 2, we give a lower bound on the phase transition threshold as a function of the scaling parameter. We also perform computational studies that suggest our bound is tight and investigate the critical density for formulas with higher clause lengths. Similar to the uniform model, on formulas with k ⩾ 3, we find that the phase transition regime corresponds to a set of formulas that are difficult to solve by backtracking search.

AAAI Conference 2017 Conference Paper

What’s Hot in Evolutionary Computation

• Tobias Friedrich
• Frank Neumann

We provide a brief overview on some hot topics in the area of evolutionary computation. Our main focus is on recent developments in the areas of combinatorial optimization and real-world applications. Furthermore, we highlight recent progress on the theoretical understanding of evolutionary computing methods.

TCS Journal 2015 Journal Article

Genetic and Evolutionary Computation

• Tobias Friedrich
• Jun He
• Thomas Jansen
• Alberto Moraglio

TCS Journal 2015 Journal Article

On the average-case complexity of parameterized clique

• Nikolaos Fountoulakis
• Tobias Friedrich
• Danny Hermelin

The k -Clique problem is a fundamental combinatorial problem that plays a prominent role in classical as well as in parameterized complexity theory. It is among the most well-known NP-complete and W[1]-complete problems. Moreover, its average-case complexity analysis has created a long thread of research already since the 1970s. Here, we continue this line of research by studying the dependence of the average-case complexity of the k -Clique problem on the parameter k. To this end, we define two natural parameterized analogs of efficient average-case algorithms. We then show that k -Clique admits both analogues for Erdős–Rényi random graphs of arbitrary density. We also show that k -Clique is unlikely to admit either of these analogs for some specific computable input distribution.

TCS Journal 2014 Journal Article

Genetic and Evolutionary Computation

• Tobias Friedrich
• Jonathan Rowe

AIJ Journal 2013 Journal Article

Approximation quality of the hypervolume indicator

• Karl Bringmann
• Tobias Friedrich

In order to allow a comparison of (otherwise incomparable) sets, many evolutionary multi-objective optimizers use indicator functions to guide the search and to evaluate the performance of search algorithms. The most widely used indicator is the hypervolume indicator. It measures the volume of the dominated portion of the objective space bounded from below by a reference point. Though the hypervolume indicator is very popular, it has not been shown that maximizing the hypervolume indicator of sets of bounded size is indeed equivalent to the overall objective of finding a good approximation of the Pareto front. To address this question, we compare the optimal approximation ratio with the approximation ratio achieved by two-dimensional sets maximizing the hypervolume indicator. We bound the optimal multiplicative approximation ratio of n points by 1 + Θ ( 1 / n ) for arbitrary Pareto fronts. Furthermore, we prove that the same asymptotic approximation ratio is achieved by sets of n points that maximize the hypervolume indicator. However, there is a provable gap between the two approximation ratios which is even exponential in the ratio between the largest and the smallest value of the front. We also examine the additive approximation ratio of the hypervolume indicator in two dimensions and prove that it achieves the optimal additive approximation ratio apart from a small ratio ⩽ n / ( n − 2 ), where n is the size of the population. Hence the hypervolume indicator can be used to achieve a good additive but not a good multiplicative approximation of a Pareto front. This motivates the introduction of a “logarithmic hypervolume indicator” which provably achieves a good multiplicative approximation ratio.

TCS Journal 2013 Journal Article

Constraint satisfaction problems: Convexity makes AllDifferent constraints tractable

• Michael Fellows
• Tobias Friedrich
• Danny Hermelin
• Nina Narodytska
• Frances Rosamond

We examine the complexity of constraint satisfaction problems that consist of a set of AllDiff constraints. Such CSPs naturally model a wide range of real-world and combinatorial problems, like scheduling, frequency allocations, and graph coloring problems. As this problem is known to be NP-complete, we investigate under which further assumptions it becomes tractable. We observe that a crucial property seems to be the convexity of the variable domains and constraints. Our main contribution is an extensive study of the complexity of Multiple AllDiff CSPs for a set of natural parameters, like maximum domain size and maximum size of the constraint scopes. We show that, depending on the parameter, convexity can make the problem tractable even though it is provably intractable in general. Interestingly, the convexity of constraints is the key property in achieving fixed parameter tractability, while the convexity of domains does not usually make the problem easier.

AIJ Journal 2013 Journal Article

Speeding up many-objective optimization by Monte Carlo approximations

• Karl Bringmann
• Tobias Friedrich
• Christian Igel
• Thomas Voß

Many state-of-the-art evolutionary vector optimization algorithms compute the contributing hypervolume for ranking candidate solutions. However, with an increasing number of objectives, calculating the volumes becomes intractable. Therefore, although hypervolume-based algorithms are often the method of choice for bi-criteria optimization, they are regarded as not suitable for many-objective optimization. Recently, Monte Carlo methods have been derived and analyzed for approximating the contributing hypervolume. Turning theory into practice, we employ these results in the ranking procedure of the multi-objective covariance matrix adaptation evolution strategy (MO-CMA-ES) as an example of a state-of-the-art method for vector optimization. It is empirically shown that the approximation does not impair the quality of the obtained solutions given a budget of objective function evaluations, while considerably reducing the computation time in the case of multiple objectives. These results are obtained on common benchmark functions as well as on two design optimization tasks. Thus, employing Monte Carlo approximations makes hypervolume-based algorithms applicable to many-objective optimization.

TCS Journal 2012 Journal Article

Approximating the least hypervolume contributor: NP-hard in general, but fast in practice

• Karl Bringmann
• Tobias Friedrich

The hypervolume indicator is an increasingly popular set measure to compare the quality of two Pareto sets. The basic ingredient of most hypervolume indicator based optimization algorithms is the calculation of the hypervolume contribution of single solutions regarding a Pareto set. We show that exact calculation of the hypervolume contribution is #P-hard while its approximation is NP-hard. The same holds for the calculation of the minimal contribution. We also prove that it is NP-hard to decide whether a solution has the least hypervolume contribution. Even deciding whether the contribution of a solution is at most ( 1 + ε ) times the minimal contribution is NP-hard. This implies that it is neither possible to efficiently find the least contributing solution (unless P = NP ) nor to approximate it (unless NP = BPP ). Nevertheless, in the second part of the paper we present a fast approximation algorithm for this problem. We prove that for arbitrarily given ε, δ > 0 it calculates a solution with contribution at most ( 1 + ε ) times the minimal contribution with probability at least ( 1 − δ ). Though it cannot run in polynomial time for all instances, it performs extremely fast on various benchmark datasets. The algorithm solves very large problem instances which are intractable for exact algorithms (e. g. , 10, 000 solutions in 100 dimensions) within a few seconds.

TCS Journal 2012 Journal Article

Convergence of set-based multi-objective optimization, indicators and deteriorative cycles

• Rudolf Berghammer
• Tobias Friedrich
• Frank Neumann

Multi-objective optimization deals with the task of computing a set of solutions that represents possible trade-offs with respect to a given set of objective functions. Set-based approaches such as evolutionary algorithms are very popular for solving multi-objective optimization problems. Convergence of set-based approaches for multi-objective optimization is essential for their success. We take an order-theoretic view on the convergence of set-based multi-objective optimization and examine how the use of indicator functions can help to direct the search towards Pareto optimal sets. In doing so, we point out that set-based multi-objective optimization working on the dominance relation of search points has to deal with a cyclic behavior that may lead to worsening with respect to the Pareto-dominance relation defined on sets. Later on, we show in which situations well-known binary and unary indicators can help to avoid this cyclic behavior and therefore guarantee convergence of the algorithm. We also study the impact of deteriorative cycles on the runtime behavior and give an example in which they provably slow down the optimization process.

IJCAI Conference 2011 Conference Paper

Approximation-Guided Evolutionary Multi-Objective Optimization

• Karl Bringmann
• Tobias Friedrich
• Frank Neumann
• Markus Wagner

Multi-objective optimization problems arise frequently in applications but can often only be solved approximately by heuristic approaches. Evolutionary algorithms have been widely used to tackle multi-objective problems. These algorithms use different measures to ensure diversity in the objective space but are not guided by a formal notion of approximation. We present a new framework of an evolutionary algorithm for multi-objective optimization that allows to work with a formal notion of approximation. Our experimental results show that our approach outperforms state-of-the-art evolutionary algorithms in terms of the quality of the approximation that is obtained in particular for problems with many objectives.

IJCAI Conference 2011 Conference Paper

Constraint Satisfaction Problems: Convexity Makes AllDifferent Constraints Tractable

• Michael Fellows
• Tobias Friedrich
• Danny Hermelin
• Nina Narodytska
• Frances Rosamond

We examine the complexity of constraint satisfaction problems that consist of a set of AllDiff constraints. Such CSPs naturally model a wide range of real-world and combinatorial problems, like scheduling, frequency allocations and graph coloring problems. As this problem is known to be NP-complete, we investigate under which further assumptions it becomes tractable. We observe that a crucial property seems to be the convexity of the variable domains and constraints. Our main contribution is an extensive study of the complexity of Multiple AllDiff CSPs for a set of natural parameters, like maximum domain size and maximum size of the constraint scopes. We show that, depending on the parameter, convexity can make the problem tractable while it is provably intractable in general.

TCS Journal 2011 Journal Article

Illustration of fairness in evolutionary multi-objective optimization

• Tobias Friedrich
• Christian Horoba
• Frank Neumann

It is widely assumed that evolutionary algorithms for multi-objective optimization problems should use certain mechanisms to achieve a good spread over the Pareto front. In this paper, we examine such mechanisms from a theoretical point of view and analyze simple algorithms incorporating the concept of fairness. This mechanism tries to balance the number of offspring of all individuals in the current population. We rigorously analyze the runtime behavior of different fairness mechanisms and present illustrative examples to point out situations, where the right mechanism can speed up the optimization process significantly. We also indicate drawbacks for the use of fairness by presenting instances, where the optimization process is slowed down drastically.

TCS Journal 2010 Journal Article

Plateaus can be harder in multi-objective optimization

• Tobias Friedrich
• Nils Hebbinghaus
• Frank Neumann

In recent years a lot of progress has been made in understanding the behavior of evolutionary computation methods for single- and multi-objective problems. Our aim is to analyze the diversity mechanisms that are implicitly used in evolutionary algorithms for multi-objective problems by rigorous runtime analyses. We show that, even if the population size is small, the runtime can be exponential where corresponding single-objective problems are optimized within polynomial time. To illustrate this behavior we analyze a simple plateau function in a first step and extend our result to a class of instances of the well-known SetCover problem.

TCS Journal 2009 Journal Article

Comparison of simple diversity mechanisms on plateau functions

• Tobias Friedrich
• Nils Hebbinghaus
• Frank Neumann

It is widely assumed and observed in experiments that the use of diversity mechanisms in evolutionary algorithms may have a great impact on its running time. Up to now there is no rigorous analysis pointing out how different diversity mechanisms influence the runtime behavior. We consider evolutionary algorithms that differ from each other in the way they ensure diversity and point out situations where the right mechanism is crucial for the success of the algorithm. The considered evolutionary algorithms either diversify the population with respect to the search points or with respect to function values. Investigating simple plateau functions, we show that using the “right” diversity strategy makes the difference between an exponential and a polynomial runtime. Later on, we examine how the drawback of the “wrong” diversity mechanism can be compensated by increasing the population size.