Loading…
Thumbnail Image

Algorithmic and structural aspects of temporal graphs

Renken, Malte

This thesis studies selected structural and algorithmic aspects of temporal graphs, which are graphs whose edges are present only at specific points in time. Temporal graphs are well suited to model a range of real-world networks whose connections frequently vary over time, such as public transport, physical proximity, or communication networks. We are particularly interested in structures related to reachability between vertices. In temporal graphs, this is a more complex concept than in static graphs, because reaching some vertex b from another vertex a requires not only a sequence of edges that forms a path from a to b, but additionally the times at which these edges are present must be in monotonically increasing order. Specifically, we investigate the following four individual aspects of temporal graphs. Temporal Voronoi games: Voronoi games, which have in the past been studied on static graphs and in Euclidean space, model a scenario in which two actors compete to reach as many vertices as possible before the other. We now define and study Voronoi games on temporal graphs. By analyzing the structure induced by these games, we discover sufficient conditions for the existence (and efficient construction) of Nash equilibria, that is, stable situations in which neither player wishes to change their current position. Connectivity in random temporal graphs: We study reachability in a simple model of random temporal graphs, which is inspired by Erdős-Rényi graphs. In this model, we find that various fine-grained degrees of temporal reachability are attained at distinct sharp density thresholds, i.e., a large random temporal graph possesses a certain reachability property (with high probability) if and only if its density is above a property-specific threshold. We further obtain thresholds for the existence of certain types of temporal spanners, i.e., subgraphs providing pairwise temporal reachability between all vertices. Temporal feedback edge sets: We consider the computational problem of removing a minimum number of connections in order to break all temporal cycles, that is, vertices reaching themselves through a circular path. On the one hand, we prove that this problem is NP-hard, even in some very restricted settings. On the other hand, we find that it becomes fixed-parameter tractable when parameterized by certain parameter combinations. Isolated cliques: We study the algorithmic complexity of finding temporal cliques, that is, sets of vertices and time intervals such that these vertices are pairwise directly connected during said time interval. Here, we focus on isolated temporal cliques, that is, temporal cliques which are only sparsely connected to the remainder of the graph. We find that for five out of six possible notions of isolation, the enumeration of these cliques is fixed-parameter tractable when parameterized by the degree of isolation.
Diese Arbeit beschäftigt sich mit ausgewählten strukturellen und algorithmischen Aspekten von temporalen Graphen, d.h. Graphen deren Kanten nur zu gewissen Zeitpunkten vorhanden sind. Temporale Graphen eignen sich zur Modellierung zahlreicher Netzwerke, deren Verbindungen stark zeitabhängig sind, wie dies z.B. im öffentlichen Personenverkehr, bei Kontaktgraphen oder Kommunikationsnetzen oft der Fall ist. Unsere Interesse gilt insbesondere der Erreichbarkeit zwischen Knoten. Dieses Konzept ist in temporalen Graphen komplexerer Natur als in statischen Graphen, denn einen Knoten b von einem anderen Knoten a aus zu erreichen, erfordert nicht nur eine Folge von Kanten, die einen Pfad von a nach b bilden, sondern zusätzlich dass die Verfügbarkeitszeiten dieser Kanten entlang des Pfades monoton steigen. Im Einzelnen werden hier die folgenden vier Aspekte temporaler Graphen näher untersucht. Temporale Voronoi-Spiele: Voronoi-Spiele wurden in der Vergangenheit auf statischen Graphen und im Euklidischen Raum analysiert. Sie modellieren ein Szenario, in dem zwei konkurrierende Akteure versuchen, möglichst viele Knoten jeweils zuerst zu erreichen. In dieser Arbeit werden Voronoi-Spiele auf temporalen Graphen eingeführt und untersucht. Eine genaue Analyse der diesen Spielen innewohnenden Struktur erlaubt es uns, hinreichende Bedingungen für die Existenz von Nash-Gleichgewichten (d.h. stabilen Situationen von denen keiner der Spieler abweichen möchte) zu finden (und diese effizient zu bestimmen). Erreichbarkeit in zufälligen temporalen Graphen: Wir untersuchen die Erreichbarkeit in einem einfachen Modell von zufälligen temporalen Graphen, das an Erdős-Rényi-Graphen angelehnt ist. Es stellt sich heraus, dass in diesem Modell verschiedene Abstufungen von temporaler Erreichbarkeit an spezifischen scharfen Dichte-Schwellwerten erreicht werden. Das bedeutet, dass ein großer zufälliger temporaler Graph gewisse Erreichbarkeitseigenschaften (mit hoher Wahrscheinlichkeit) genau dann besitzt, wenn seine Dichte den jeweiligen Schwellwert überschreitet. Ferner ermitteln wir solche Dichte-Schwellwerte auch für die Existenz verschiedener Arten von Subgraphen, die temporale Erreichbarkeit zwischen allen Knoten herstellen. Temporale Feedback-Kanten-Mengen: Es geht hier um das (algorithmische) Problem, eine kleinstmögliche Anzahl an Verbindungen aus einem gegebenen temporalen Graphen zu entfernen um damit alle temporalen Kreise zu unterbrechen, d.h. sodass anschließend kein Knoten mehr sich selbst über einen Rundweg erreichen kann. Zum einen stellen wir fest, dass dieses Problem selbst in einigen sehr eingeschränkten Szenarien NP-schwer ist, zum anderen zeigen wir aber auch fixed-parameter tractability für gewisse Parameterkombinationen. Isolierte Cliquen: Eine temporale Clique besteht aus einer Knotenmenge und einem Zeitintervall mit der Eigenschaft, dass ebendiese Knoten während des besagten Zeitintervalls paarweise durch Kanten verbunden sind. Wir betrachten insbesondere isolierte temporale Cliquen, d.h. temporale Cliquen, die nur schwach mit dem restlichen Graphen verbunden sind. Wir zeigen für fünf der sechs möglichen Isolationsbegriffe, dass eine Auflistung isolierter temporaler Cliquen fixed-parameter tractable bzgl. des Parameters Isolationsgrad ist.