Classic graph problems made temporal – a parameterized complexity analysis

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.