Given a class of graphs F, we say that a graph G is universal for F, or F-universal, if every H ∊ F is contained in G as a subgraph. The construction of sparse universal graphs for various families F has received a considerable amount of attention. One is particularly interested in tight F-universal graphs, i.e., graphs whose number of vertices is equal to the largest number of vertices in a graph from F. Arguably, the most studied case is that when F is some class of trees. Given integers n and Δ, we denote by T(n, Δ) the class of all n-vertex trees with maximum degree at most Δ. In this work, we show that every n-vertex graph satisfying certain natural expansion properties is T(n, Δ)-universal or, in other words, contains every spanning tree of maximum degree at most Δ. Our methods also apply to the case when Δ is some function of n. The result has a few very interesting implications. Most importantly, since random graphs are known to be good expanders, we obtain that the random graph G(n, p) is asymptotically almost surely (a.a.s.) universal for the class of all bounded degree spanning (that is, n-vertex) trees provided that p ≥ cn−1/3 log n where c > 0 is a constant. Moreover, a corresponding result holds for the random regular graph of degree pn. In fact, we show that if Δ satisfies log n ≤ Δ ≤ n1/3, then the random graph G(n, p) with p ≥ cΔn−1/3 log n and the random r-regular n-vertex graph with r ≥ cΔn2/3 log n are a.a.s. universal for T(n, Δ). Another interesting consequence is the existence of locally sparse n-vertex graphs that are universal for T(n, Δ). For Δ ∊ O(1), we show that one can (randomly) construct n-vertex T(n, Δ)-universal graphs with clique number at most five. This complements the construction of Bhatt, Chung, Leighton, and Rosenberg (1989), whose T(n, Δ)-universal graphs with merely O(n) edges contain large cliques of size Ω(Δ). We also derive some lower bounds and show that there exist very good expanders which are not universal for T(n, Δ). In particular, we see that there are expanders of minimum degree Ω(n/log n) which are not T(n, c√n)-universal. Finally, we show robustness of random graphs with respect to being universal for T(n, Δ) in the context of the Maker-Breaker tree-universality game.

We regard the classical problem how the (1+1) Evolutionary Algorithm optimizes an arbitrary linear pseudo-Boolean function. We show that any such function is optimized in time (1 + o(1)) 1.39en ln (n), where n is the length of the bit string. We also prove a lower bound of (1 -o(1))en ln(n), which in fact holds for all functions with a unique global optimum. This shows that for linear functions, even though the optimization behavior might differ, the resulting runtimes are very similar. Our experimental results suggest that the true optimization times are even closer than what the theoretical guarantees promise.

In this paper, we present a new representation for individuals in the single-source shortest path problem. Contrary to previous approaches, it has the natural property that different vertex degrees do not induce unfairness in the mutation step. In particular, at any time each edge has roughly the same probability of being added to or removed from the current individual.

Drift analysis is one of the strongest tools in the analysis of evolutionary algorithms. Its main weakness is that it is often very hard to find a good drift function.

In this article, we formulate for the first time the notion of a quantum evolutionary algorithm. In fact we define a quantum analogue for any elitist (1+1) randomized search heuristic. The quantum evolutionary algorithm, which we call (1+1) quantum evolutionary algorithm (QEA), is the quantum version of the classical (1+1) evolutionary algorithm (EA), and runs only on a quantum computer. It uses Grover search [13] to accelerate the search for improved offsprings.To understand the speedup of the (1+1) QEA over the (1+1) EA, we study the three well known pseudo-Boolean optimization problems OneMax, LeadingOnes, and Discrepancy. We show that although there is a speedup in the case of OneMax and LeadingOnes in the quantum setting, the speedup is less than quadratic. For Discrepancy, we show that the speedup is at best constant.The reason for this inconsistency is due to the difference in the probability of making a successful mutation. On the one hand, if the probability of making a successful mutation is large then quantum acceleration does not help much. On the other hand, if the probabilities of making a successful mutation is small then quantum enhancement indeed helps.

This work is devoted to the study of the typical structure of a random map. Maps are planar graphs embedded in the plane. We investigate the degree sequences of random maps from families of a certain type, which, among others, includes fundamental map classes like those of biconnected maps, 3-connected maps, and triangulations. In particular, we develop a general framework that allows us to derive relations and exact asymptotic expressions for the expected number of vertices of degree k in random maps from these classes, and also provide accompanying large deviation statements. Extending the work of Gao and Wormald (Combinatorica, 2003) on random general maps, we obtain as results of our framework precise information about the number of vertices of degree k in random biconnected, 3-connected, loopless, and bridgeless maps.

Rigorous runtime analyses of evolutionary algorithms (EAs) mainly investigate algorithms that use elitist selection methods. Two algorithms commonly studied are Randomized Local Search (RLS) and the (1+1) EA and it is well known that both optimize any linear pseudo-Boolean function on n bits within an expected number of O(n log n) fitness evaluations. In this paper, we analyze variants of these algorithms that use fitness proportional selection.

Neumann and Witt (2006) analyzed the runtime of the basic ant colony optimization (ACO) algorithm 1-Ant on pseudo-Boolean optimization problems. For the problem OneMax they showed how the runtime depends on the evaporation factor. In particular, they proved a phase transition from exponential to polynomial runtime. In this work, we simplify the view on this problem by an appropriate translation of the pheromone model. This results in a profound simplification of the pheromone update rule and, by that, a refinement of the results of Neumann and Witt. In particular, we show how the exponential runtime bound gradually changes to a polynomial bound inside the phase of transition.

We propose and analyze a novel genotype to represent walk and cycle covers in graphs, namely matchings in the adjacency lists. This representation admits the natural mutation operator of adding a random match and possibly also matching the former partners.