Algorithm Engineering Research Seminar (Winter 2024)

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.

In this talk, I will give you a short overview of the results we obtained on these two problems in my Master’s thesis. We’ll have graphs, algorithms, randomization, tables for Tobias, and, dare I say it, even a few experiments resulting in pretty plots.

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.

Ipe is an awesome tool for creating high-quality LaTeX-supported (graph) drawings, slides, and posters — a visual alternative to TIKZ. In this "workshop", we’ll cover the basics of how to use Ipe and explore what it can do through hands-on examples and ideas from everyone in the room. I’ll start by showing some of the things I’ve made with Ipe, but the real fun will be seeing what tricks and tips others have to share. Whether you’re totally new to Ipe or already a pro, you’re welcome to join! Bring a laptop (with Ipe downloaded ipe.otfried.org/), your questions, and any ideas you want to try out. This session is designed for bachelor, master, PhD and postdoc students, as well as all LaTeX enthusiasts. Let’s dive into Ipe together and see where our creativity takes us!

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 the talk 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. 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/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.