Prof. Dr. Tobias Friedrich

Research Seminar (Winter Term 2022)

<previous seminar | next seminar>


A series of talks on current research and interesting topics in algorithm engineering and theoretical computer science. Everyone is welcome to attend talks. 

If you want to give a talk about a topic in algorithm engineering or theoretical computer science, please write an e-mail to Dr. Andreas Göbel or Nadym Mallek.


For announcements of talks, subscribe to our mailing list.

Talks (click on title to show abstract)

18.10. 13:30A-1.2Jonathan Gadea Harder

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 NP-hard. 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:15K2.03 (hybrid)Nikhil Kumar
Given a graph G with edge capacities and multiple source-sink 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 cut-condition is sufficient for routing demands. We consider the following generalization of this setting and prove an approximate max flow-min cut theorem: for every demand edge, there exists a face containing both its end points. We show that the cut-condition 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:00K2.03 (hybrid)Simon Wietheger

Fair Correlation Clustering is a graph clustering objective and the fair variant of the well-known 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 non-edges inside clusters, is minimized while guaranteeing the same distribution of colors in every cluster.

While the problem is NP-hard 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 NP-hard 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:15K2.03 (hybrid)Michelle Döring

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 so-called 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:15K2.03 (hybrid)Julian Berger

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 real-world 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 game-theoretic properties in a number of different sets of metrics.

1.12. 15:15K2.03 (hybrid)Kirill Simonov

We introduce a general method for obtaining fixed-parameter 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 n-vertex 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 matroid-rank condition instead of the colors.

8.12 15:15K2.03 (hybrid)Hans Gawendowicz

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

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ős-Ré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 non-negligible 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:15K2.03 (hybrid)Marcos Kiwi

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 well-connected "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 forest-like structure.

Joint work with Markus Schepers (Johannes-Gutenberg-U. Mans, Mainz, Germany) and John Sylvester (U. of Liverpool, UK).

26.1. 15:15K2.03 (hybrid)Simon Krogmann

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 non-cooperative two-sided 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 NP-hard to decide. On the positive side, we provide a simple and efficient algorithm to compute 3-approximate subgame perfect equilibria.

02.2. 15:15K2.03 (hybrid)George Skretas


09.2. 15:15K2.03 (hybrid)Voula Machaira

We present the non-FIFO time-dependent graph model with REalistic vehicle eXchange times (REX) for schedule-based multimodal public transport, along with a novel query algorithm called TRIP-based LAbel-correction propagation (TRIPLA) algorithm that efficiently solves the realistic earliest-arrival routing problem. The REX model possesses all strong features of previous time-dependent graph models without suffering from their deficiencies. It handles non-negligible exchanges from one vehicle to another, as well as supports non-FIFO instances which are typical in public transport, without compromising space efficiency. We conduct a thorough experimental evaluation with real-world data which demonstrates that TRIPLA significantly outperforms all state-of-the-art query algorithms for multimodal earliest-arrival routing in schedule-based public transport.

16.2. 15:15K2.03 (hybrid)BP-project