The prediction of future connections in evolving networks is a fundamental challenge in network science with wide-ranging applications. Link prediction has been addressed through various approaches, including methods based on proximity scores and modern machine learning models. This thesis introduces and evaluates an alternative approach grounded in game theory. We propose a novel class of link predictors based on the Network Creation Game (NCG), a model where rational agents strategically form edges to maximize their individual utility. By reframing an agent's strategic incentive to create a link as a proximity score, this work translates theoretical models of network formation into practical predictive tools. We systematically explore variants of this NCG predictor by combining different definitions for connection benefits with various edge price functions that model heterogeneous connection costs. To assess performance, we conduct a comprehensive empirical study, benchmarking the NCG predictor against a suite of established methods on several real-world dynamic networks. These include the arXiv collaboration networks from the foundational study by Liben-Nowell and Kleinberg, extended temporal snapshots of this data, and the Internet's autonomous systems graph. Our results demonstrate that the NCG-based prediction methods are highly competitive, frequently matching or exceeding the performance of established methods. The most effective NCG models are consistently those that reward the formation of triangles, highlighting the importance of reinforcing local network structure. Ultimately, this work demonstrates that viewing link formation as a strategic game offers a competitive and transparent framework for predicting how networks evolve.

Temporal graphs are graphs whose edges are labelled with times at which they are active. Their time-sensitivity provides a useful model of real networks, but renders many problems studied on temporal graphs more computationally complex than their static counterparts. To contend with this, there has been recent work devising parameters for which temporal problems become tractable. One such parameter is vertex-interval-membership (VIM) width. Broadly, this gives a bound on the number of vertices we need to keep track of at any given time to solve many problems. Our contributions are two-fold. Firstly, we introduce a new parameter, tree-interval-membership (TIM) width, that generalises both VIM width and several existing generalisations. Secondly, we provide meta-algorithms for both VIM and TIM width which can be used to prove fixed-parameter-tractability for large families of problems, bypassing the need to give involved dynamic programming arguments for every problem. In doing this, we provide a characterisation of problems in FPT with respect to both parameters.

This paper revisits the classic “gossip problem,” where people call one another at scheduled times with the goal that eventually everyone has heard all information. While it is NP-hard to decide if it is possible to find a schedule of calls when we are given a fixed graph (who can talk to whom), I'm this paper we show that the problem becomes tractable when we are only given how many calls each person can make (we can choose who they call and when). We give a complete set of rules that determine exactly when such gossip networks are possible, and provide fast constructive algorithms.

The bachelor's project will introduce our project partner (IVU), the tram depot we hope to improve scheduling for, the challenges it poses, and how we plan to overcome them using an ILP. We have implemented this ILP over the past few months and hope to show its inner workings. We will present our modeling of the problem, the tightness of the solution space, how we have handled a rocky start, and our next steps.

In a typical bus depot, managing the daily flow of vehicles is a significant operational challenge. As hundreds of buses return throughout the day, they must be assigned to parking lanes that operate under strict FIFO constraints. The goal is to ensure that every scheduled departure is covered by a bus of the correct type. This task is increasingly complicated by the transition to electric fleets, which introduces specific charging and energy constraints that must be integrated into the decision-making process. Furthermore, because arrivals often deviate from their planned schedules due to traffic or disruptions, these assignments must often be made in real-time. In this talk, I will present the Electric Bus Dispatching Problem and discuss the solutions we developed using both Integer Linear Programming and heuristic algorithms. Using real-world data from a German public transport company, I will discuss how different algorithmic approaches handle these constraints and evaluate the impact of infrastructure parameters, such as parking capacity and charging power, on overall service reliability.

Colour Refinement is a combinatorial method that distinguishes vertices in graphs based on their local neighborhood structure. By encoding these local properties into vertex colours that are refined iteratively, the process eventually stabilises into a final colouring which serves as an isomorphism test on a large class of graphs. The central complexity parameter of the algorithm is the number of iterations required to reach stabilisation. For n-vertex graphs, the upper bound is n−1. We call graphs that attain this maximum long-refinement graphs. Their final colourings are discrete, meaning every vertex is uniquely identified by its colour. For a long time, it was not clear whether such graphs actually exist. My talk provides an overview of the history of this graph class and reports on recent work towards a full characterisation of it. By restricting our scope to graphs with small degrees, we have constructed infinite families of long-refinement graphs. Furthermore, by reverse-engineering connections between colour classes, we obtained a complete classification of long-refinement graphs with small (or, equivalently, large) degrees. This analysis offers deep insights into the dynamics of the refinement process, revealing that all long-refinement graphs with maximum degree 3 can be described by compact strings over a remarkably small alphabet. The talk is based on collaborations with Brendan D. McKay and T. Devini de Mel.

Every system implementation involves risk, requiring decision makers to determine acceptable levels for a given application. We model risk using a cumulative risk function F, where F(n) denotes the expected annual frequency of accidents causing at least n fatalities. In this talk, we study voting over cumulative risk functions. Voters rank candidate systems by their associated cumulative risk functions, and we analyze the structure of these rankings under different assumptions on preference formation. We then show how we can use these structures to efficiently compute sets of acceptable candidates, namely the proportional veto core.

Sequence data are (usually temporally) ordered finite or infinite streams of events that are instances of a multi-dimensional schema. Systems which deal with sequence data usually use queries to detect situations of interest. However, finding such queries from historical sequence data is notoriously hard and is often assumed to be a non-automated task. To overcome this, some existing approaches in the field of complex event processing strive for automatically discovering event queries. Though, among others, the complexity of the mining problem remains open. In this talk, we discuss multi-dimensional subsequence-queries with wildcards and gap-size constraints (mswg-queries, for short) as a tool for querying event traces. These queries consist of a pattern of variables and so-called types, enriched by different kinds of window constraints. We study the task of discovering an mswg-query that best describes a given sample, i.e. a finite set of traces. For that, we provide an algorithm solving this problem, and briefly investigate its complexity. Our analysis identifies the subroutine for solving the matching problem (i.e., deciding whether a given query q matches in a given trace t) as the only potential bottleneck. tl;dr (foundations): Given a set of strings, instead of searching for a fixed pattern in each string, we tackle the inverse problem: discovering a pattern that best explains the data. tl;dr (data&ai): To recognize situations of interest in sequential data, we first need to learn what “interesting behavior” looks like by automatically discovering patterns in the data.

In this talk, we will develop an approach to simultaneous embeddability in temporal sequences of graphs, inspired by graph minor theory. Our main result is a classification theorem for 2-connected temporal sequences: we identify five obstruction classes and show that every 2-connected temporal sequence is either simultaneously embeddable or admits a sequence of improvements leading to an obstruction. This structural insight leads to a polynomial-time algorithm for deciding the simultaneous embeddability of 2-connected temporal sequences. The restriction to 2-connected sequences is necessary, as the problem is NP-hard for connected graphs, while trivial for 3-connected graphs. More broadly, our result demonstrates the applicability of graph minor techniques to temporal graph structures. It also provides a foundation for future investigations into related analogues, such as simultaneous treewidth and simultaneous representability for sequences of matroids.

Voula: Greedy Routing Reachability Games

Today's networks consist of many autonomous entities that follow their own objectives, i.e., smart devices or parts of large AI systems, that are interconnected. Given the size and complexity of most communication networks, each entity typically only has a local view and thus must rely on a local routing protocol for sending and forwarding packets. A common solution for this is greedy routing, where packets are locally forwarded to a neighbor in the network that is closer to the packet's destination. In this paper we investigate a game-theoretic model with autonomous agents that aim at forming a network where greedy routing is enabled. The agents are positioned in a metric space and each agent tries to establish as few links as possible, while maintaining that it can reach every other agent via greedy routing. Thus, this model captures how greedy routing networks are formed without any assumption on the distribution of the agents or the specific employed greedy routing protocol. Hence, it distills the essence that makes greedy routing work. We study two variants of the model: with directed edges or with undirected edges. For the former, we show that equilibria exist, have optimal total cost, and that in Euclidean metrics they can be found efficiently. However, even for this simple setting computing optimal strategies is NP-hard. For the much more challenging setting with undirected edges, we show for the realistic setting with agents in 2D Euclidean space that the price of anarchy is between 1.75 and 1.8 and for higher dimensions it is less than 2. Also, we show that best response dynamics may cycle, but that in Euclidean space almost optimal approximate equilibria can be computed in polynomial time. Moreover, for 2D Euclidean space, these approximate equilibria outperform the well-known Delaunay triangulation.

Merlin: Metric Hedonic Games on the Line

Hedonic games are fundamental models for investigating the formation of coalitions among a set of strategic agents, where every agent has a certain utility for every possible coalition of agents it can be part of. To avoid the intractability of defining exponentially many utilities for all possible coalitions, many variants with succinct representations of the agents' utility functions have been devised and analyzed, e.g., modified fractional hedonic games by Monaco et al. [JAAMAS 2020]. We extend this by studying a novel succinct variant that is related to modified fractional hedonic games. In our model, each agent has a fixed type-value and an agent's cost for some given coalition is based on the differences between its value and those of the other members of its coalition. This allows to model natural situations like athletes forming training groups with similar performance levels or voters that partition themselves along a political spectrum. In particular, we investigate natural variants where an agent's cost is defined by distance thresholds, or by the maximum or average value difference to the other agents in its coalition. For these settings, we study the existence of stable coalition structures, their properties, and their quality in terms of the price of anarchy and the price of stability. Further, we investigate the impact of limiting the maximum number of coalitions. Despite the simple setting with metric distances on a line, we uncover a rich landscape of models, partially with counter-intuitive behavior. Also, our focus on both swap stability and jump stability allows us to study the influence of fixing the number and the size of the coalitions. Overall, we find that stable coalition structures always exist but that their properties and quality can vary widely.