Algorithm Engineering Research Seminar (Winter 2025)

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.

TBA

TBA