# Classic graph problems made temporal – a parameterized complexity analysis

**Size:**218 pages

**Format:**14,8 x 21,0 cm

**Publishing year:**2020

**Reihe:**Foundations of Computing ; 13

**ISBN**978-3-7983-3172-3

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.