Search

Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph G, a temporal graph is represented by assigning a set of integer time-labels to every edge e of G, indicating the discrete time steps at which e is active. We introduce and study the complexity of a natural temporal extension of the classical graph problem Maximum Matching, taking into account the dynamic nature of temporal graphs. In our problem, Maximum Temporal Matching, we are looking for the largest possible number of time-labeled edges (simply time-edges) (e,t) such that no vertex is matched more than once within any time window of Δ consecutive time slots, where Δ ∈ ℕ is given. The requirement that a vertex cannot be matched twice in any Δ-window models some necessary "recovery" period that needs to pass for an entity (vertex) after being paired up for some activity with another entity. We prove strong computational hardness results for Maximum Temporal Matching, even for elementary cases. To cope with this computational hardness, we mainly focus on fixed-parameter algorithms with respect to natural parameters, as well as on polynomial-time approximation algorithms., LIPIcs, Vol. 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), pages 27:1-27:14

Published in print by Universitätsverag der TU Berlin, ISBN 978-3-7983-3172-3 (ISSN 2199-5249), This thesis investigates the parameterized computational complexity of six classic graph problems lifted to a temporal setting. More specifically, we consider problems defined on temporal graphs, that is, a graph where the edge set may change over a discrete time interval, while the vertex set remains unchanged. Temporal graphs are well-suited to model dynamic data and hence they are naturally motivated in contexts where dynamic changes or time-dependent interactions play an important role, such as, for example, communication networks, social networks, or physical proximity networks. The most important selection criteria for our problems was that they are well-motivated in the context of dynamic data analysis. Since temporal graphs are mathematically more complex than static graphs, it is maybe not surprising that all problems we consider in this thesis are NP-hard. We focus on the development of exact algorithms, where our goal is to obtain fixed-parameter tractability results, and refined computational hardness reductions that either show NP-hardness for very restricted input instances or parameterized hardness with respect to “large” parameters. In the context of temporal graphs, we mostly consider structural parameters of the underlying graph, that is, the graph obtained by ignoring all time information. However, we also consider parameters of other types, such as ones trying to measure how fast the temporal graph changes over time. In the following we briefly discuss the problem setting and the main results. Restless Temporal Paths. A path in a temporal graph has to respect causality, or time, which means that the edges used by a temporal path have to appear at non-decreasing times. We investigate temporal paths that additionally have a maximum waiting time in every vertex of the temporal graph. Our main contributions are establishing NP-hardness for the problem of finding restless temporal paths even in very restricted cases, and showing W[1]-hardness with respect to the feedback vertex number of the underlying graph. Temporal Separators. A temporal separator is a vertex set that, when removed from the temporal graph, destroys all temporal paths between two dedicated vertices. Our contribution here is twofold: Firstly, we investigate the computational complexity of finding temporal separators in temporal unit interval graphs, a generalization of unit interval graphs to the temporal setting. We show that the problem is NP-hard on temporal unit interval graphs but we identify an additional restriction which makes the problem solvable in polynomial time. We use the latter result to develop a fixed-parameter algorithm with a “distance-to-triviality” parameterization. Secondly, we show that finding temporal separators that destroy all restless temporal paths is Σ-P-2-hard. Temporal Matchings. We introduce a model for matchings in temporal graphs, where, if two vertices are matched at some point in time, then they have to “recharge” afterwards, meaning that they cannot be matched again for a certain number of time steps. In our main result we employ temporal line graphs to show that finding matchings is NP-hard even on instances where the underlying graph is a path. Temporal Coloring. We lift the classic graph coloring problem to the temporal setting. In our model, every edge has to be colored properly (that is, the endpoints are colored differently) at least once in every time interval of a certain length. We show that this problem is NP-hard in very restricted cases, even if we only have two colors. We present simple exponential-time algorithms to solve this problem. As a main contribution, we show that these algorithms presumably cannot be improved significantly. Temporal Cliques and s-Plexes. We propose a model for temporal s-plexes that is a canonical generalization of an existing model for temporal cliques. Our main contribution is a fixed-parameter algorithm that enumerates all maximal temporal s-plexes in a given temporal graph, where we use a temporal adaptation of degeneracy as a parameter. Temporal Cluster Editing. We present a model for cluster editing in temporal graphs, where we want to edit all “layers” of a temporal graph into cluster graphs that are sufficiently similar. Our main contribution is a fixed-parameter algorithm with respect to the parameter “number of edge modifications” plus the “measure of similarity” of the resulting clusterings. We further show that there is an efficient preprocessing procedure that can provably reduce the size of the input instance to be independent of the number of vertices of the original input instance., In dieser Dissertation untersuchen wir die parametrisierte Berechnungskomplexität von sechs klassischen Graphproblemen, die in einen temporalen Kontext gestellt werden. Formaler ausgedrückt betrachten wir Probleme, die auf temporalen Graphen definiert sind, wobei temporale Graphen aus einer unveränderlichen Knotenmenge bestehen, zusammen mit einer Kantenmenge, die sich über einen diskreten Zeitraum hinweg verändern darf. Temporale Graphen eignen sich besonders gut zum Modellieren dynamischer Daten und sind daher in Situationen von Bedeutung, in denen dynamische Veränderungen oder zeitabhängige Interaktionen eine wichtige Rolle spielen. Beispiele hierfür sind das Betrachten von Kommunikationsnetzwerken, sozialen Netzwerken oder Netzwerken, deren Interaktionen räumliche Annäherungen modellieren. Das wichtigste Auswahlkriterium für unsere Problemstellungen war, dass sie in Kontexten der Analyse dynamischer Daten wohlmotiviert sind. Da temporale Graphen mathematisch gesehen komplexer sind als statische Graphen, ist es vielleicht nicht sehr überraschend, dass alle Probleme, die wir in dieser Dissertation betrachten, NP-schwer sind. Wir konzentrieren uns auf die Entwicklung exakter Algorithmen, wobei wir versuchen FPT-Resultate zu erzielen oder durch spezialisierte Reduktionen zu zeigen, dass das betrachtete Problem NP-schwer auf sehr eingeschränkten Instanzen ist, oder berechnungsschwer im parametrisierten Sinne bezüglich möglichst „großer“ Parameter ist. Im Kontext temporaler Graphen betrachten wir in erster Linie Strukturparameter des unterliegenden Graphen, das heißt des Graphen, den man erhält, wenn man alle Zeitinformationen ignoriert. Allerdings studieren wir auch andere Parameter, zum Beispiel solche, die das Ausmaß der zeitlichen Veränderung eines temporalen Graphen messen. Im Folgenden geben wir einen kurzen Überblick über unsere Problemstellungen und wichtigsten Ergebnisse. Restless Temporal Paths. Ein Pfad in einem temporalen Graph muss Kausalität oder Zeit respektieren. Dies bedeutet, dass die Kanten, die von dem temporalen Pfad benutzt werden, nicht zu abnehmenden Zeitpunkten erscheinen dürfen. Wir untersuchen temporale Pfade, die darüber hinaus eine maximal erlaubte Wartezeit in allen Knoten haben. Unsere Hauptresultate sind, dass Pfade dieser Art zu finden NP-schwer ist, sogar in sehr restriktiven Instanzen, und dass das Problem W[1]-schwer bezüglich der kreiskritischen Knotenzahl des unterliegenden Graphen ist. Temporal Separators. Ein temporaler Separator ist eine Knotenmenge, die, wenn sie aus einem temporalen Graph entfernt wird, alle temporalen Pfade zwischen zwei iausgewählten Knoten zerstört. Wir erzielen hier zwei Hauptresultate: Auf der einen Seite untersuchen wir die Berechnungskomplexität des Findens von temporalen Separatoren in temporalen Einheitsintervallgraphen, einer Verallgemeinerung von Einheitsintervallgraphen im temporalen Kontext. Wir zeigen, dass das Problem auf temporalen Einheitsintervallgraphen NP-schwer ist, aber identifizieren eine weitere Einschränkung, die es erlaubt, das Problem in Polynomzeit zu lösen. Auf Letzterem aufbauend entwickeln wir einen FPT-Algorithmus, der eine „Distanz-zur-Trivialität“-Parametrisierung nutzt. Auf der anderen Seite zeigen wir, dass das Finden temporaler Separatoren, die alle ruhelosen temporalen Pfade zerstören, Σ-P-2-schwer ist. Temporal Matchings. Wir führen ein Modell für Matchings in temporalen Graphen ein, bei dem sich zwei Knoten „erholen“ müssen, nachdem sie zu einem bestimmten Zeitpunkt einander zugeordnet wurden. Das heißt, für eine gewisse Zeit können diese Knoten nicht wieder einander zugeordnet werden. Wir nutzen das Konzept von temporalen Kantengraphen, um zu zeigen, dass das Finden von temporalen Matchings NP-schwer ist, selbst wenn der unterliegende Graph ein Pfad ist. Temporal Coloring. Wir übertragen das klassische Knotenfärbungsproblem in den temporalen Rahmen. In unserem Modell muss jede Kante in jedem Zeitfenster einer bestimmten Größe mindestens einmal gültig gefärbt sein, also beide Endpunkte eine andere Farbe haben. Wir zeigen, dass dieses Problem schon auf sehr eingeschränkten Instanzen NP-schwer ist – sogar für zwei Farben. Wir beschreiben einfache Exponentialzeitalgorithmen für dieses Problem. Eines unserer Hauptresultate ist, dass diese Algorithmen vermutlich nicht signifikant verbessert werden können. Temporal Cliques and s-Plexes. Wir stellen ein Modell für temporale s-Plexe vor, das eine kanonische Verallgemeinerung eines existierenden Modells für temporale Cliquen ist. Unser Hauptresultat ist ein FPT-Algorithmus, der alle maximalen temporalen s-Plexe aufzählt, wobei wir eine temporale Variante von Degeneriertheit von Graphen als Parameter benutzen. Temporal Cluster Editing. Wir stellen ein Modell für Clustereditierung in temporalen Graphen vor, bei dem wir alle „Schichten“ eines temporalen Graphens in hinreichend ähnliche Cluster überführen wollen. Unsere Hauptergebnisse sind zum einen ein FPT-Algorithmus bezüglich des Parameters „Anzahl der Editierungen plus Ähnlichkeit der Cluster“. Zum anderen geben wir eine effiziente Vorverarbeitungsmethode an, welche die Größe der Eingabeinstanz beweisbar so reduziert, dass sie unabhängig von der Anzahl der Knoten der ursprünglichen Instanz ist.

We study the NP-hard graph problem Collapsed k-Core where, given an undirected graph G and integers b, x, and k, we are asked to remove b vertices such that the k-core of remaining graph, that is, the (uniquely determined) largest induced subgraph with minimum degree k, has size at most x. Collapsed k-Core was introduced by Zhang et al. [AAAI 2017] and it is motivated by the study of engagement behavior of users in a social network and measuring the resilience of a network against user drop outs. Collapsed k-Core is a generalization of r-Degenerate Vertex Deletion (which is known to be NP-hard for all r >= 0) where, given an undirected graph G and integers b and r, we are asked to remove b vertices such that the remaining graph is r-degenerate, that is, every its subgraph has minimum degree at most r. We investigate the parameterized complexity of Collapsed k-Core with respect to the parameters b, x, and k, and several structural parameters of the input graph. We reveal a dichotomy in the computational complexity of Collapsed k-Core for k = 3. For the latter case it is known that for all x >= 0 Collapsed k-Core is W[P]-hard when parameterized by b. We show that Collapsed k-Core is W[1]-hard when parameterized by b and in FPT when parameterized by (b + x) if k

Funnels are a new natural subclass of DAGs. Intuitively, a DAG is a funnel if every source-sink path can be uniquely identified by one of its arcs. Funnels are an analog to trees for directed graphs that is more restrictive than DAGs but more expressive than in-/out-trees. Computational problems such as finding vertex-disjoint paths or tracking the origin of memes remain NP-hard on DAGs while on funnels they become solvable in polynomial time. Our main focus is the algorithmic complexity of finding out how funnel-like a given DAG is. To this end, we study the NP-hard problem of computing the arc-deletion distance to a funnel of a given DAG. We develop efficient exact and approximation algorithms for the problem and test them on synthetic random graphs and real-world graphs., Submitted to ISCO 2018

Motivated by the recent rapid growth of research for algorithms to cluster multi-layer and temporal graphs, we study extensions of the classical Cluster Editing problem. In Multi-Layer Cluster Editing we receive a set of graphs on the same vertex set, called layers and aim to transform all layers into cluster graphs (disjoint unions of cliques) that differ only slightly. More specifically, we want to mark at most d vertices and to transform each layer into a cluster graph using at most k edge additions or deletions per layer so that, if we remove the marked vertices, we obtain the same cluster graph in all layers. In Temporal Cluster Editing we receive a sequence of layers and we want to transform each layer into a cluster graph so that consecutive layers differ only slightly. That is, we want to transform each layer into a cluster graph with at most k edge additions or deletions and to mark a distinct set of d vertices in each layer so that each two consecutive layers are the same after removing the vertices marked in the first of the two layers. We study the combinatorial structure of the two problems via their parameterized complexity with respect to the parameters d and k, among others. Despite the similar definition, the two problems behave quite differently: In particular, Multi-Layer Cluster Editing is fixed-parameter tractable with running time k^{O(k + d)} s^{O(1)} for inputs of size s, whereas Temporal Cluster Editing is W[1]-hard with respect to k even if d = 3.

The Firefighter Problem was proposed in 1995 [16] as a deterministic discrete-time model for the spread (and containment) of a fire. Its applications reach from real fires to the spreading of deseases and the containment of floods. Furthermore, it can be used to model the spread of computer viruses or viral marketing in communication networks. In this work, we study the problem from a game-theorical perspective. Such a context seems very appropriate when applied to large networks, where entities may act and make decisions based on their own interests, without global coordination. We model the Firefighter Problem as a strategic game where there is one player for each time step who decides where to place the firefighters. We show that the Price of Anarchy is linear in the general case, but at most 2 for trees. We prove that the quality of the equilibria improves when allowing coalitional cooperation among players. In general, we have that the Price of Anarchy is in O( n / k ) where k is the coalition size. Furthermore, we show that there are topologies which have a constant Price of Anarchy even when constant sized coalitions are considered.

The h-index is an important bibliographic measure used to assess the performance of researchers. Van Bevern et al. [Artif. Intel., to appear] showed that, despite computational worst-case hardness results, substantial manipulation of the h-index of Google Scholar author profiles is possible by merging articles. Complementing this work, we study the opposite operation, the splitting of articles, which is arguably the more natural operation for manipulation and which is also allowed within Google Scholar. We present numerous results on computational complexity (from linear-time algorithms to parameterized computational hardness results) and empirically indicate that at least small improvements of the h-index by splitting merged articles are easily achievable.

Finding a vertex subset in a graph that satisfies a certain property is one of the most-studied topics in algorithmic graph theory. The focus herein is often on minimizing or maximizing the size of the solution, that is, the size of the desired vertex set. In several applications, however, we also want to limit the "exposure" of the solution to the rest of the graph. This is the case, for example, when the solution represents persons that ought to deal with sensitive information or a segregated community. In this work, we thus explore the (parameterized) complexity of finding such secluded vertex subsets for a wide variety of properties that they shall fulfill. More precisely, we study the constraint that the (open or closed) neighborhood of the solution shall be bounded by a parameter and the influence of this constraint on the complexity of minimizing separators, feedback vertex sets, F-free vertex deletion sets, dominating sets, and the maximization of independent sets.