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 non-linear 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.

Partitioning a large group of employees into teams can prove difficult because unsatisfied employees may want to transfer to other teams. In this case, the team (coalition) formation is unstable and incentivizes deviation from the proposed structure. Such a coalition formation scenario can be modeled in the framework of hedonic games and a significant amount of research has been devoted to the study of stability in such games. Unfortunately, stable coalition structures are not guaranteed to exist in general and their practicality is further hindered by computational hardness barriers. We offer a new perspective on this matter by studying a random model of hedonic games. For three prominent stability concepts based on single-agent deviations, we provide a high probability analysis of stability in the large agent limit.

Our first main result is an efficient algorithm that outputs an individually and contractually Nash-stable partition with high probability. Our second main result is that the probability that a random game admits a Nash-stable partition tends to zero. Our approach resolves the two major downsides associated with individual stability and contractual Nash stability and reveals agents acting single-handedly are usually to blame for instabilities.

This is joined work with Sonja Kraiczy.

Given an instance of a scheduling problem where we want to start executing jobs as soon as possible, it is advantageous if a scheduling algorithm emits the first parts of its solution early, in particular before the algorithm completes its work. Therefore, in this position paper, we analyze core scheduling problems in regards to their enumeration complexity, i. e. the computation time to the first emitted schedule entry (preprocessing time) and the worst case time between two consecutive parts of the solution (delay).

Specifically, we look at scheduling instances that reduce to ordering problems. We apply a known incremental sorting algorithm for scheduling strategies that are at their core comparison-based sorting algorithms and translate corresponding upper and lower complexity bounds to the scheduling setting. For instances with n jobs and a precedence DAG with maximum degree Δ, we incrementally build a topological ordering with O(n) preprocessing and O(Δ) delay. We prove a matching lower bound and show with an adversary argument that the delay lower bound holds even in case the DAG has constant average degree and the ordering is emitted out-of-order in the form of insert operations.

We complement our theoretical results with experiments that highlight the improved time-to-first-output and discuss research opportunities for similar incremental approaches for other scheduling problems.

The Weisfeiler-Leman (WL) dimension of a graph parameter f is the minimum k such that, if G1 and G2 are indistinguishable by the k-dimensional WL-algorithm then f(G1)=f(G2). The WL-dimension of f is ∞ if no such k exists. We study the WL-dimension of graph parameters characterised by the number of answers from a fixed conjunctive query to the graph. Given a conjunctive query φ, we quantify the WL-dimension of the function that maps every graph G to the number of answers of φ in G. The works of Dvorák (J. Graph Theory 2010), Dell, Grohe, and Rattan (ICALP 2018), and Neuen (ArXiv 2023) have answered this question for full conjunctive queries, which are conjunctive queries without existentially quantified variables. For such queries φ, the WL-dimension is equal to the treewidth of the Gaifman graph of φ.

In this work, we give a characterisation that applies to all conjunctive qureies. Given any conjunctive query φ, we prove that its WL-dimension is equal to the semantic extension width sew(φ), a novel width measure that can be thought of as a combination of the treewidth of φ and its quantified star size, an invariant introduced by Durand and Mengel (ICDT 2013) describing how the existentially quantified variables of φ are connected with the free variables. Using the recently established equivalence between the WL-algorithm and higher-order Graph Neural Networks (GNNs) due to Morris et al. (AAAI 2019), we obtain as a consequence that the function counting answers to a conjunctive query φ cannot be computed by GNNs of order smaller than sew(φ).

In this session, our three young and ambitious scientists will each present us briefly a paper they felt like showing us. Each talk will be 5 minutes long and invite for discussion. The titles of those talks are:
- "What is Best for Students, Numerical Scores or Letter Grades?" From Michelle
- "COCO: the black-box testbed" From Sherry
- A surprise talk from Andreas

Many real-world networks, like transportation networks and social networks, are dynamic in the sense that the edge set may change over time, but these changes are known in advance. This behavior is captured by the temporal graphs model, which has recently become a trending topic in theoretical computer science. A core open problem in the field is to prove the existence of linear-size temporal spanners in temporal cliques, i.e., sparse subgraphs of complete temporal graphs that ensure all-pairs reachability via temporal paths. So far, the best known result is the existence of temporal spanners with O(n log n) many edges. We present significant progress towards proving that linear-size temporal spanners exist in all temporal cliques.

We adapt techniques used in previous works and heavily expand and generalize them. This allows to show that the existence of a linear spanner in cliques and bi-cliques is equivalent and also provide a simpler and more intuitive proof of the O(n log n) bound. Moreover, we use our novel approach to show that a large class of temporal cliques, called edge-pivotable graphs, admit linear-size temporal spanners. To contrast this, we investigate other classes of temporal cliques that do not belong to the class of edge-pivotable graphs. We introduce two such graph classes and we develop novel techniques for establishing the existence of linear temporal spanners in these graph classes as well. This work was done in last year’s Master’s project.

In the Demand Strip Packing problem (DSP), we are given a set of jobs, each specified by a processing time and a demand. The task is to schedule all jobs such that they are finished before some deadline D while minimizing the peak demand, i.e., the maximum total demand of tasks executed at any point in time. DSP is closely related to the Strip Packing problem (SP), in which we are given a set of axis-aligned rectangles that must be packed into a strip of fixed width while minimizing the maximum height. DSP and SP are known to be NP-hard to approximate to within a factor below ³⁄₂.

To achieve the essentially best possible approximation guarantee, we prove a structural result. Any instance admits a solution with peak demand at most (³⁄₂+ε)*OPT satisfying one of two properties. Either (i) the solution leaves a gap for a job with demand OPT and processing time O(ε D) or (ii) all jobs with demand greater than ^OPT⁄₂ appear sorted by demand in immediate succession. We then provide two efficient algorithms that find a solution with maximum demand at most (³⁄₂ε)*OPT in the respective case. A central observation that sets our approach apart from previous ones, is that the properties (i) and (ii) need not be efficiently decidable: We can simply run both algorithms and use whichever solution is the better one.

While most theoretical run time analyses of discrete randomized search heuristics focus on finite search spaces, we consider the search space $\Z^n$. Understanding this search space is especially relevant for developing better algorithms for mixed-integer black box optimization (MI-BBO) problems.

We consider as a fitness functions the distance to the (unique) non-zero optimum a (based on the l1-metric) and study the (1+1) EA which mutates by applying a step-operator on each component that is determined to be varied. For changing by ±, we show that the expected optimization time is Θ(n . (|a|_{∞} + \log(|a|_H))). In particular, the time is linear in |a|_{∞}, a measure of distance between starting point and target $a$. Employing a different step operator which chooses a step size from a distribution so heavy-tailed that the expectation is infinite, we get an optimization time of O(n . \log^2 (|a|_1) . [(\log (\log (|a|_1))]^{1 + ε})$.

Furthermore, we show that RLS with step size adaptation achieves an optimization time of Θ(n . \log(|a|_1)) and that l1-symmetric operators (as suggested by Rudolph'94) require a time at least linear in |a|_1.

A distance oracle for a graph G is a data structure that, when queried with two vertices s and t, returns an estimate of their distance d(s,t) in G. The oracle has stretch (α, β) if the estimate satisfies d(s,t) ≤ d̂(s,t) ≤ α · d(s,t) + β. In this talk, I will discuss construction of new (α, β)-distance-oracles with sub-quadratic space that, for a small additive error β > 0, allow one to make the multiplicative stretch α arbitrarily small. These are the first sub-quadratic space DOs with (1 + ε, O(1))-stretch, generalizing Agarwal and Godfrey’s results for sparse graphs [SODA 2013] to general undirected graphs.

In this talk, I will provide an introduction to parameterised counting problems and present a selection of the most influential results and techniques that have been introduced in the last decade. Particular focus will be put on graph motif parameters and the "homomorphism basis", an algorithmic framework introduced by Curticapean, Dell, and Marx (STOC 17) that allowed for charting the (parameterised) complexity landscape of a multitude of (in)famous counting problems such as subgraph and induced subgraph counting, first-order model counting, and counting constraint satisfaction problems.

Moreover, I will discuss a couple of open problems that are either fundamental for our structural understanding of parameterised counting or that have prominently been studied in recent years but evaded a resolution so far. The talk does not assume any background in counting complexity theory.

We provide the first results showing that Steiner Tree Packing is fixed-parameter tractable by structural parameters. In Steiner Tree Packing, we are given a graph G, a terminal set T ⊆ V (G), and a demand d ∈ N+. We want to decide whether there are d edge-disjoint trees contained in G which each connect the terminal set. This problem is of high practical relevance for VLSI circuit design and computer networking. However, it is NP-hard as soon as |T| ≥ 3 or d ≥ 2, meaning that it is unlikely that there exists an efficient algorithm solving all relevant instances. Previous research has approached this problem by providing heuristic or approximate algorithms to circumvent this barrier. If exact solutions are required, this approach—by its nature—falls flat.

We approach this barrier by instead restricting the set of instances which we aim to solve using the tools of structural parameterization. To achieve this, we first generalize the notion of the augmented graph from Edge-Disjoint Paths to Generalized Steiner Tree Packing. The augmented graph for an instance extends the input graph to reflect which connections are desired. Then, we extend all known algorithms for Edge-Disjoint Paths parameterized by a structural parameter, which have fixed-parameter tractable running time to Generalized Steiner Tree Packing. In some cases, we even improve upon the known running times. We then show, how these generalized algorithms can be applied to Steiner Tree Packing.

Specifically, we show that - Steiner Tree Packing is fixed-parameter tractable parameterized by tree-cut width as well as by fracture number, which constitute the first known results that Steiner Tree Packing is fixed-parameter tractable by a structural parameter; - Generalized Steiner Tree Packing is fixed-parameter tractable by the fracture number as well as the tree-cut width of the augmented graph and fixed-parameter tractable by the slim tree-cut width of the input graph. This affirmatively settles the open question, whether Edge-Disjoint Paths is fixed-parameter tractable by the tree-cut width of the augmented graph.

Combined, these results significantly broaden the class of instances for all three problems, where an exact polynomial time algorithm is known. Additionally, the results for Generalized Steiner Tree Packing parameterized with respect to the augmented graph are the first results making use of the augmented graph for a problem where the terminals can be arbitrary vertex sets.

A temporal graph is a graph whose edges are only present at certain points in time. These graphs received a growing attention over the past two decades, due to their ability to model various types of dynamic networks. On the theoretical side, temporal graphs are quite different from static graphs. For instance, reachability (defined in terms of paths that traverses edges in chronological order) is not transitive. This and other features have important consequences, both structural and algorithmic, most questions being computationally hard.

In this talk, I will review some basic results in this young field, with a focus on sparse spanning substructures. Such structures do not always exist (yet, they are guaranteed in a probabilistic sense). If time permits, I will also mention aspects related to the enumeration of temporal graphs and some properties of their groups of automorphisms.

Most of us PhD students of the AE chair end up working pretty independently most of the time. Sure, we share results, bounce around ideas, and have brainstorming sessions, but a lot of the journey happens quietly in our own heads.

In this short and light hearted talk, I will try to give perspective on what I have been doing in the past 2 years. First, I will explain why and how I had to slightly change research directions and how I looked into several different topics before finding the one. Second, I will tell you how I landed on the particular problem I work on now. And, finally, I will try to describe how and why the angles and methods used to tackle that problem have evolved over the months.

this talk isn’t just a chance for me to reflect on this phase of my PhD—it’s also about showing the bigger picture that probably won’t make it into any paper, and that I might forget if I didn’t take a moment to talk about it now.

In this session, three randomly picked researchers and a guest Professor will give you a short talk regarding something that is important to them: The titles of those talks are:
- The Freshest JuniorProfessor of HPI by Niclas (Title by Nadym Mallek)
- Menger's Analogue Misquoted: How Citation Shapes the Study of Temporal Graphs by Michelle
- Random and quasirandom growth models on Z² by Tobias
- Optimal mixing of the down-up walk on independent sets of a given size by Marcus

Finding a subgraph that fulfills certain properties is a common thread of many classical algorithmic problems, such as independent set, shortest path, or minimum spanning tree. For real-world applications, where privacy is of concern, or when looking for segregated communities in social networks, it is natural to limit the size of the neighborhood of the subgraph. This was formalized as the Secluded Π-Subgraph problem, where we are asked to find a maximum weight vertex set S ⊆ V(G) that satisfies a property Π and is k-secluded, i.e., S has at most |N(S)| ≤ k neighboring vertices. Equivalently, we can treat the neighborhood as a separator between the subgraph and the remaining graph. This connection gives rise to elegant applications and extensions of techniques from parameterized complexity, such as important separators and recursive understanding. All in all, we have a good understanding for which properties Π the problem is W[1]-hard when parameterized by k and which algorithmic techniques allow us to construct efficient FPT-algorithms.

However, while it has long been accepted that directed graph separation problems, such as Directed Feedback Vertex Set or Directed Multicut, are interesting and worth studying, all of the previous work on secluded subgraphs is focussed only on undirected graphs. We close this gap by introducing secluded subgraph problems on directed graphs parameterized by the neighborhood size, transferring and generalizing previously studied properties, such as acyclicity and connectivity. We explore different neighborhood definitions, that is, we consider only incoming edges, only outgoing edges, or all neighboring vertices.

In contrast to the undirected case, we show that the widely-studied Secluded F -Free Subgraph problem becomes W[1]-hard for almost all F with only unidirectional neighborhood, where F is a finite set of forbidden induced subgraphs. Even requiring connected solutions is not enough to achieve fixed-parameter tractability. The same holds for Secluded DAG, a directed version of Secluded Tree.

We consider more connectivity problems and show that Secluded Strongly Connected Subgraph is FPT for bidirectional neighborhood using recursive understanding. With the same technique, we also develop a non-uniform FPT-algorithm for finding secluded d-edge-connected subgraphs in undirected graphs.

Furthermore, we develop faster branching algorithms proving that the undirected Secluded Cliqe problem is FPT with runtime 1.6181knO(1); the previous algorithms based on important separators require at least time 4knO(1). We go on to generalize these branching algorithms to tournaments in directed graphs and to find graphs with a constant independence number in both directed and undirected graphs. Furthermore, we show how previously intractable directed problems become efficiently solvable in FPT-time in graphs with a small independence number.