In the classical setting evolutionary algorithms (EAs) are used to compute a single solution of high quality with respect to the objective function or a set of trade-off solutions in the field multi-objective optimization where one deals with multiple, usually conflicting objectives. Traditionally, diversity preservation is introduced as a means to prevent premature convergence. In many engineering applications and in the field of algorithm selection/configuration however, it is beneficial to produce a set of solutions that is (1) of high quality and (2) diverse with respect to the search space and/or some features of the given problem. Evolutionary Diversity Optimization enables the computation of a large variety of new and innovative solutions that are unlikely to be produced by traditional evolutionary computation methods for single-objective or multi-objective optimization. In this talk, we will give an introduction into evolutionary diversity optimization and highlight some recent results from the areas of communication networks and health.

We consider intersection graphs of disks of radius r in the hyperbolic plane. Unlike the Euclidean setting, these graph classes are different for different values of r, where very small r corresponds to an almost-Euclidean setting and r∈Ω(logn) corresponds to a firmly hyperbolic setting. We observe that larger values of r create simpler graph classes, at least in terms of separators and the computational complexity of the Independent Set problem.

TBA

Algorithms for analyzing spreading processes help us combat everything from infectious diseases to misinformation online. In the important graph discovery problem, we seek to discover the entire structure of a graph from infection data. Similarly, in the source detection problem, we aim to find the source of the spreading process. Recent research—for example by Michelle and George in our group—has begun to consider spreading processes in temporal graphs to more accurately model their behavior in real-world networks, which often change over time. Yet, there is no prior work on graph discovery or source detection on temporal graphs.

An adjacency labeling scheme for a class of graphs C defines, for any n-vertex G in C, an assignment of labels to each vertex in G so that adjacency in G is determined by a (fixed) function of the two labels of the endpoints. It is desirable to have these labels as short as possible. By a counting argument, if there are |C_n| many n-vertex graphs in C then any adjacency labeling scheme needs labels with at least (log|C_n|)/n many bits.

For many natural classes (e.g. planar, bounded twin-width, bounded degeneracy) this lower bound is tight, and the Implicit Graph Conjecture (IGC), which first appeared in 1988, postulated that for all hereditary classes containing at most 2^{O(n\log n)} many n-vertex graphs (factorial classes), the lower bound is tight (i.e. they have labeling schemes of size O(log n)). Hatami & Hatami recently annihilated this conjecture, using the probabilistic method to construct a factorial class requiring almost square root n size labels.

After a gentle introduction to labeling schemes, I will outline Hatami & Hatami's proof and how we have adapted & expanded their method in two directions. The first direction is speed, where we show that even classes growing at barely factorial speed can need large labels. The second is strength of closure, where we show that the IGC fails even for monotone factorial classes (monotone closure is significantly more restrictive than hereditary closure).

Joint work with Édouard Bonnet, Julien Duron, Viktor Zamaraev & Maksim Zhukovskii

TBA

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 kk-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)⋅O(∣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).

In the Coordinated Motion Planning problem, sometimes referred to as Multiagent Pathfinding (MAPF), we are given a graph together with starting positions and destinations of k distinct robots. The goal is to route a set of k robots to their destinations without any collision while minimizing a certain objective target - prominently the number of time steps in the schedule, i.e., the makespan, or the total length traveled by the robots. In this talk, we will discuss some recent (parameterized) algorithmic results related to the problem and its generalizations. The talk will be based on my joint work with Argyris Deligkas, Robert Ganian, Iyad Kanj, and M.S. Ramanujan.