18.10. 13:30  A1.2  Jonathan Gadea Harder  Facility Location Games with heterogenous customers
Facility Location Games consist of facilities which choose where to place themselves and customers who decide where to be served. This is in contrast to the facility location optimization problem, which deals with one service provider placing facilities in order to maximize profits. Since the customer decision of where to be served depends upon where the facilities place themselves, this is a sequential game, which is in contrast to simultaneous games where all players decide on their strategy simultaneously.
We study Facility Location Games on networks where on each vertex there is a certain amount of customers placed. These customers are binary coloured and have a preference for other customers of the same colours. This means that when they can decide between two facilities, they will choose the one with a bigger ratio of customers of the same colour up to a certain threshold 0
In this work we show that calculating the welfare optimum for both facilities, given a customer strategy, and customers, given a facility placement, is NPhard. We further analyse the existence of Nash equilibria for this setting, show that the Price of Anarchy is 2 for the facilities and provide an upper bound of 2 on the Price of Anarchy for the customers.
Last, we prove that subgame perfect equilibria (SPE) exist for two classes of graphs. The first one being graphs without vertices of degree 0 where the number of facilities exceeds the number of locations n, where SPE always exist. On the class of grid networks, where the number of customers of each colour for every location is uniformly sampled between 1 and x in N and with at most n/36  sqrt(n)/6 + b facilities, b being a logarithmic term, we prove that the probability that no SPE exists is below 1/n.

27.10. 15:15  K2.03 (hybrid)  Nikhil Kumar  An Approximate Generalization of the OkamuraSeymour Theorem
Given a graph G with edge capacities and multiple sourcesink pairs, each with an associated demand, the multicommodity flow problem is to route all demands simultaneously without violating edge capacities. We consider the problem of multicommodity flows in planar graphs. Okamura and Seymour showed that if all the demands are incident on one face, then the cutcondition is sufficient for routing demands. We consider the following generalization of this setting and prove an approximate max flowmin cut theorem: for every demand edge, there exists a face containing both its end points. We show that the cutcondition is sufficient for routing Ω(1)fraction of all the demands. To prove this, we give a L_1 embedding of the planar metric which approximately preserves distance between all pair of points on the same face.

11.11. 10:00  K2.03 (hybrid)  Simon Wietheger  Fair Correlation Clustering in Forests
Fair Correlation Clustering is a graph clustering objective and the fair variant of the wellknown Correlation Clustering. It is motivated by applications involving sensitive attributes like skin color or gender that must not be over or underrepresented in any cluster. In this model, the vertices of the input graph are colored to represent the manifestations of a sensitve attribute. The task is to partition the set of vertices such that the number of disagreements, i.e., edges between different clusters and nonedges inside clusters, is minimized while guaranteeing the same distribution of colors in every cluster.
While the problem is NPhard on general graphs, we investigate whether there are efficiently solvable instances. To this end, we focus on various kinds of forests as normal, "unfair" Correlation Clustering is efficiently solvable there. Our results show that Fair Correlation Clustering is NPhard already on very restricted classes of forests. Nevertheless, we provide algorithms that have polynomial running time under certain assumptions on the color distribution of the vertex set.
Additionally, we give a PTAS and investigate a setting with a less strict definition of fairness.

17.11. 15:15  K2.03 (hybrid)  Michelle Döring  Margin of Victory for Weighted Tournament Solutions
Determining how close a winner of an election is to becoming a loser, or distinguishing between different possible winners of an election, are major problems in Computational Social Choice. We tackle these problems for socalled weighted tournaments by generalizing the notion of Margin of Victory (MoV) for unweighted tournament solutions by Brill et al. to weighted tournament solutions. For these, the MoV of a winner (resp. loser) is the total weight that needs to be changed in the tournament to make them a loser (resp. winner). We study three weighted tournament solutions: Borda's rule, the weighted Uncovered Set, and Split Cycle. For all three rules, we analyse the complexity of computing the MoV, and provide structural insight into the MoV by investigating three properties:
monotonicity, consistency regarding the weighted covering relation, and consistency regarding the degree of alternatives. Lastly, we provide upper and lower bounds on the MoV and analyse the expressiveness of the MoV values for each of the three tournament solutions using experimental results on tournaments of varying sizes.

24.11. 15:15  K2.03 (hybrid)  Julian Berger  Greedy Routing Network Creation Games
Network Creation Games are a popular tool to study the emergence of networks created by selfish agents, such as the Internet.
Despite navigating between nodes for the transport of information or matter being essential in many realworld networks, previous works have largely disregarded how resulting networks can be navigated. To navigate arbitrary networks however, information about the global network structure is required. One simple way to avoid the need for such global information is greedy routing, where in each step a neighboring node that is closer to the destination than the current node is selected.
To this end, we introduce a network creation model where agents can only rely on greedy paths to reach other agents. This ensures that greedy routing is always possible in equilibrium networks, while realistically modeling the incentives of individual agents when all navigation in the network is assumed to operate greedily.
We examine different variants of that model and analyze the existence of equilibria, computational hardness, as well as other gametheoretic properties in a number of different sets of metrics.

1.12. 15:15  K2.03 (hybrid)  Kirill Simonov  FixedParameter Tractability of Maximum Colored Path and Beyond
We introduce a general method for obtaining fixedparameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is as follows. We present a randomized algorithm, that given a colored nvertex undirected graph, vertices s and t, and an integer k, finds an (s,t)path containing at least k different colors in time 2^k poly(n). This is the first FPT algorithm for this problem, and it generalizes the algorithm of Björklund, Husfeldt, and Taslaman [SODA 2012] on finding a path through k specified vertices. It also implies the first 2^k poly(n) time algorithm for finding an (s,t)path of length at least k. Our method yields FPT algorithms for even more general problems, extending to a collection of (s,t)paths instead of a single path, and an arbitrary matroidrank condition instead of the colors.

8.12 15:15  K2.03 (hybrid)  Hans Gawendowicz  Temporal Network Creation
Network Creation is an important and widely studied game theoretic topic. With temporal graphs receiving more and more attention in recent years, we think it is time to introduce temporal elements into the Network Creation Game domain. We aim at starting a new research direction by combinining both fields into network creation game models on temporal graphs.
We start by developing a simple rechability game where agents are nodes on a temporal host network that can buy edges towards other agents in order to maintain a temporal path to every other agent. We then analyze the model from a game theoretic viewpoint by characterizing equilibria and dynamic properties (e.g. existence of improving response cycles) and bounding the price of anarchy.
As this project is work in progress, we would like to give you an overview of our current state as well as engage in discussions about new ideas and potential approaches that we can try.

15.12. 15:15    (virtual)  Viktor Zamaraev  Sharp thresholds in random simple temporal graphs
A graph whose edges only appear at certain points in time is called a temporal graph (among other names). Such a graph is temporally connected if each ordered pair of vertices is connected by a path which traverses edges in chronological order (i.e., a temporal path). In this work, we consider a simple model of random temporal graph, obtained from an ErdősRényi random graph G_{n,p} by considering a random permutation π of the edges and interpreting the ranks in π as presence times.
Temporal reachability in this model exhibits a surprisingly regular sequence of thresholds. In particular, we show that at p=logn/n any fixed pair of vertices can a.a.s. reach each other; at 2logn/n at least one vertex (and in fact, any fixed vertex) can a.a.s. reach all others; and at 3logn/n all the vertices can a.a.s. reach each other, i.e., the graph is temporally connected. Furthermore, the graph admits a temporal spanner of size 2n+o(n) as soon as it becomes temporally connected, which is nearly optimal as 2n−4 is a lower bound. This result is significant because temporal graphs do not admit spanners of size O(n) in general (Kempe et al, STOC 2000). In fact, they do not even admit spanners of size o(n^2) (Axiotis et al, ICALP 2016). Thus, our result implies that the obstructions found in these works, and more generally, all nonnegligible obstructions, must be statistically insignificant: nearly optimal spanners always exist in random temporal graphs.
All the above thresholds are sharp. Carrying the study of temporal spanners further, we show that pivotal spanners — i.e., spanners of size 2n−2 made of two spanning trees glued at a single vertex (one descending in time, the other ascending subsequently) — exist a.a.s. at 4logn/n, this threshold being also sharp. Finally, we show that optimal spanners (of size 2n−4) also exist a.a.s. at p=4logn/n.
This is a joint work with Arnaud Casteigts (University of Bordeaux), Michael Raskin (Technical University of Munich), Malte Renken (Technical University of Berlin)

19.1. 15:15  K2.03 (hybrid)  Marcos Kiwi  Cover and Hitting Times of Hyperbolic Random Graphs
We study random walks on the giant component of Hyperbolic Random Graphs
(HRGs), in the regime when the degree distribution obeys a power law
with exponent in the range (2,3). In particular, we focus on the
expected times for a random walk to hit a given vertex or visit, i.e.
cover, all vertices. We show that up to multiplicative constants: the
cover time is n*(log(n))^2, the maximum hitting time is n*log(n), and
the average hitting time is n. The first two results hold in expectation
and a.a.s. and the last in expectation (with respect to the HRG). We
prove these results by determining the effective resistance either
between an average vertex and the wellconnected "center" of HRGs or
between an appropriately chosen collection of extremal vertices. We
bound the effective resistance by the energy dissipated by carefully
designed network flows associated to a tiling of the hyperbolic plane on
which we overlay a forestlike structure.
Joint work with Markus Schepers (JohannesGutenbergU. Mans,
Mainz, Germany) and John Sylvester (U. of Liverpool, UK).

26.1. 15:15  K2.03 (hybrid)  Simon Krogmann  Strategic Facility Location with Clients that Minimize Total Waiting Time
The first part of this talk will be about the AAAI paper with the abstract below, afterwards I will talk about our current research direction with atomic unsplittable clients and more.
We study a noncooperative twosided facility location game in which facilities and clients behave strategically. This is in contrast to many other facility location games in which clients simply visit their closest facility. Facility agents select a location on a graph to open a facility to attract as much purchasing power as possible, while client agents choose which facilities to patronize by strategically distributing their purchasing power in order to minimize their total waiting time. Here, the waiting time of a facility depends on its received total purchasing power. We show that our client stage is an atomic splittable congestion game, which implies existence, uniqueness and efficient computation of a client equilibrium. Therefore, facility agents can efficiently predict client behavior and make strategic decisions accordingly. Despite that, we prove that subgame perfect equilibria do not exist in all instances of this game and that their existence is NPhard to decide. On the positive side, we provide a simple and efficient algorithm to compute 3approximate subgame perfect equilibria.

02.2. 15:15  K2.03 (hybrid)  George Skretas  Intro to simple Distributed Algorithms 
09.2. 15:15  K2.03 (hybrid)  Voula Machaira  REX: A Realistic TimeDependent Model for Multimodal Public Transport
We present the nonFIFO timedependent graph model with REalistic vehicle eXchange times (REX) for schedulebased multimodal public transport, along with a novel query algorithm called TRIPbased LAbelcorrection propagation (TRIPLA) algorithm that efficiently solves the realistic earliestarrival routing problem. The REX model possesses all strong features of previous timedependent graph models without suffering from their deficiencies. It handles nonnegligible exchanges from one vehicle to another, as well as supports nonFIFO instances which are typical in public transport, without compromising space efficiency. We conduct a thorough experimental evaluation with realworld data which demonstrates that TRIPLA significantly outperforms all stateoftheart query algorithms for multimodal earliestarrival routing in schedulebased public transport.

16.2. 15:15  K2.03 (hybrid)  BPproject members  Algorithm Auditing
In this talk, the bachelor project members will present their progress on algorithm auditing via statistical hypothesis testing.

23.2. 15:15  K2.03 (hybrid)  Thomas Bläsius  Recognizing Unit Disk Graphs in Hyperbolic Geometry is ∃RComplete
A graph G is a (Euclidean) unit disk graph if it is the intersection graph of unit disks in the Euclidean plane R². Recognizing them is known to be ∃Rcomplete, i.e., as hard as solving a system of polynomial inequalities. In this talk we describe a simple framework to translate ∃Rhardness reductions from the Euclidean plane R² to the hyperbolic plane H². We apply our framework to prove that the recognition of unit disk graphs in the hyperbolic plane is also ∃Rcomplete.

2.3. 15:15  K2.03 (hybrid)  Nadym Mallek  The Multicut problem in seriesparallel graphs
In this presentation, we will first introduce the famous mincut maxflow problem and how to solve it before diving into the realm of NPhardness and its generalization, the Multicommodityflow Multicut problem. After this quick overview of the situation with some easy and intuitive examples, we will discuss and describe the method used in an article published by some members of the Algorithm Engineering Chair in APPROX 2022. This paper tells us about how to have an approximated solution for the multicut problem by exploiting as best as we can the structural properties of seriesparallel graphs and their tree decomposition.

9.3. 15:15    (virtual)  Zef Segal  Periodicals in Motion: Using Algorithms and Network Analysis to Research 19th Century Press
In recent years, the socalled "digital humanities," i.e., the study of the humanities with the aid of computers, have gained in importance. My current research, the idea of which I will present in the seminar, examines processes of uniformity and diversity in 19thcentury societies through an extensive corpus analysis of hundreds of thousands of issues of American newspapers between 1840 and 1884. The study employs several computational approaches and techniques to identify and characterize the structure, content, and dynamics of journalistic networks in America. Among other techniques, we use tools developed for plagiarism detection to identify textual reuse and topic modeling to identify clusters of content in time and space. The overall result is a network of relationships among newspapers in time and space that will enable us to identify the directionality and pace of news flows. This study was recently awarded a fouryear Israel Science Foundation (ISF) grant.
Besides for the historical issues it raises, this study of the interaction between the American media and political, ideological, social, and technological developments raises many questions about databases. How to process the many variables associated with this network, how to represent the network and its relationships, and how to make the transition between data and historical understanding.
In this talk I will present both methods (plagiarism detection and topic modeling) and their affordances for the study of historical networks. At the same time, I will point out the difficulties that arise from the implementation of digital tools for historical research.

14.3. 13:30  K2.03 (hybrid)  Daniel Schmand  Prophet Inequalities and Bicriteria Nash Flows over Time
We discuss two different problems over time. First, we introduce an overtime variant of the wellknown prophet inequality with i.i.d. random variables. Instead of stopping with one realized value at some point in the process, we decide in each step how long we select the current value. We cannot select another value until this period is over. The goal is to maximize the expectation of the sum of selected values. We describe the structure of the optimal stopping rule and give upper and lower bounds on the prophetinequality.  Which, in online algorithms terminology, corresponds to bounds on the competitive ratio of an online algorithm.
In the second problem, we consider a variant of the well studied Nash Flows over Time, where users do not aim to reach the sink as fast as possible. Instead, we consider the model where uses aim to take a cheapest route while arriving at the sink before a given deadline. We provide results on the structure of Nash flows and bounds on the price of anarchy.
