scieee Science in your language
[en] (orig)
Vol:.(1234567890)
Algorithmica (2021) 83:2754–2802
https://doi.org/10.1007/s00453-021-00831-w
1 3
Finding Temporal Paths Under Waiting Time Constraints
ArnaudCasteigts1· Anne‑SophieHimmel2· HendrikMolter2·
PhilippZschoche2
Received: 23 October 2020 / Accepted: 30 April 2021
© The Author(s) 2021
Abstract
Computing a (short) path between two vertices is one of the most fundamental prim-
itives in graph algorithmics. In recent years, the study of paths in temporal graphs,
that is, graphs where the vertex set is fixed but the edge set changes over time,
gained more and more attention. A path is time-respecting, or temporal, if it uses
edges with non-decreasing time stamps. We investigate a basic constraint for tem-
poral paths, where the time spent at each vertex must not exceed a given duration
𝛥
,
referred to as
𝛥
-restless temporal paths. This constraint arises naturally in the mod-
eling of real-world processes like packet routing in communication networks and
infection transmission routes of diseases where recovery confers lasting resistance.
While finding temporal paths without waiting time restrictions is known to be doa-
ble in polynomial time, we show that the “restless variant” of this problem becomes
computationally hard even in very restrictive settings. For example, it is W[1]-hard
when parameterized by the distance to disjoint path of the underlying graph, which
implies W[1]-hardness for many other parameters like feedback vertex number
and pathwidth. A natural question is thus whether the problem becomes tractable
in some natural settings. We explore several natural parameterizations, presenting
FPT algorithms for three kinds of parameters: (1) output-related parameters (here,
the maximum length of the path), (2) classical parameters applied to the underlying
graph (e.g., feedback edge number), and (3) a new parameter called timed feedback
vertex number, which captures finer-grained temporal features of the input temporal
graph, and which may be of interest beyond this work.
Keywords Temporal graphs· Disease spreading· Waiting-time policies· Restless
temporal paths· Timed feedback vertex set· NP-hard problems· Parameterized
algorithms
Arnaud Casteigts was supported by the ANR, Project ESTATE (ANR-16-CE25-0009-03). Anne-
Sophie Himmel was supported by the DFG, Project FPTinP (NI 369/16). Hendrik Molter was
supported by the DFG, Project MATE (NI 369/17).
* Philipp Zschoche
zschoc[email protected]
Extended author information available on the last page of the article
2755
1 3
Algorithmica (2021) 83:2754–2802
1 Introduction
A highly successful strategy to control (or eliminate) outbreaks of infectious dis-
eases is contact tracing [25]—whenever an individual is diagnosed positively, every
person who is possibly infected by this individual is put into quarantine. However,
the viral spread can be too fast to be traced manually, e.g., if the disease is trans-
mittable in a pre-symptomatic (or asymptomatic) stage, then it seems likely that
an individual already caused infection chains when diagnosed positively. Hence,
large-scale digital systems are recommended which use physical proximity networks
based on location and contact data[29]—this allows fast and precise contact trac-
ing while avoiding the harmful effect of mass quarantines to society[29]. Physical
proximity networks can be understood as temporal graphs1 [18, 37, 39, 46, 51], that
is, graphs where the vertex set (individuals) remains static but the edge set (physical
contacts) may change over time. In this paper, we extend the literature on reachabil-
ity in temporal graphs [5, 7, 11, 14, 17, 44, 50, 61] by a computational complexity
analysis of an important variation of one of the most fundamental combinational
problems arising in the above mentioned scenario: given a temporal graph and two
individualss andz, is a chain of infection from s to z possible, that is, is there a tem-
poral path from s to z? In particular, we use a reachability concept that captures the
standard 3-state SIR-model (Susceptible-Infected-Recovered), a canonical spreading
model for diseases where recovery confers lasting resistance[8, 45, 54].
In temporal graphs, the basic concepts of paths and reachability are defined in a
time-respecting way[44]: a (strict) temporal path, also called “journey”, is a path
that uses edges with non-decreasing (increasing) time steps. To represent infection
chains in the SIR-model, we restrict the time of “waiting” or “pausing” at each inter-
mediate vertex to a prescribed duration. We call these paths restless temporal paths.
They model infection transmission routes of diseases that grant immunity upon
recovery[38]: An infected individual can transmit the disease until it is recovered
(reflected by bounded waiting time) and it cannot be infected a second time after-
wards since then it is immune (reflected by considering path instead of walk: every
vertex can only be visited at most once). Another natural example of restless tempo-
ral paths is delay-tolerant networking among mobile entities, where the routing of a
packet is performed over time and space by storing the packet for a limited time at
intermediate nodes.
In the following we give an example to informally describe our problem setting.2
In Fig.1 we are given the depicted temporal graph, vertices s and z, and the time
bound
𝛥=2
. We are asked to decide whether there is a restless temporal path from
s to z, that is, a path which visits each vertex at most once and pauses at most
𝛥
units
of time between consecutive hops. Here, (s,d,b,z) is a feasible solution, but (s,b,z)
is not because the waiting time at b exceeds
𝛥
. The walk (s,b,c,d,b,z) is not a valid
solution because it visits vertexb twice. Finally (s,a,c,d,b,z) is also a feasible
solution.
1 Also known as time-varying graphs, evolving graphs, or link streams.
2 We refer to Sect.2 for a formal definition.
2756 Algorithmica (2021) 83:2754–2802
1 3
1.1 Related Work
Several types of waiting time constraints have been considered in the temporal
graph literature. An empirical study by Pan and Saramäki [56] based on phone
calls datasets observed a threshold in the correlation between the duration of
pauses between calls and the ratio of the network reached over a spreading process.
Casteigts et al. [19] showed a dramatic impact of waiting time constraints to the
expressivity of a temporal graph, when considering such a graph as an automaton
and temporal paths as words. In the context of temporal flows, Akrida et al. [4]
considered a concept of “vertex buffers”, which however pertains to the quantity of
information that a vertex can store, rather than a duration. Enrightetal.[26] consid-
ered deletion problems for reducing temporal connectivity. More closely related to
our work, Himmeletal.[11] studied a variant of restless temporal paths where sev-
eral visits to the same vertex are allowed, i.e., restless temporal walks. They showed,
among other things, that such walks can be computed in polynomial time.
Many path-related problems have been studied in the temporal setting and the
nature of temporal paths significantly increases the computational complexity of
many of them (compared to their static counterparts). In the temporal setting, reach-
ability is not an equivalence relation among vertices, which makes many problems
more complicated. For example, finding a maximum temporally connected com-
ponent is NP-hard[14]. We further have that in a temporal graph, spanning trees
may not exist. In fact, even the existence of sparse spanners (i.e., subgraphs with
o(n2)
-many edges ensuring temporal connectivity) is not guaranteed[7], unless the
underlying graph is complete[20], and computing a minimum-cardinality spanner is
APX-hard[3, 50]. Yet another example is the problem of deciding whether there are
k disjoint temporal paths between two given vertices. In a seminal article, Kempe
etal.[44] showed that this problem, whose classical analogue is (again) polynomial-
time solvable, becomes NP-hard. They further investigated the related problem of
finding temporal separators, which is also NP-hard[30, 44, 62]. Deciding whether
there exists a separator of a given size that cuts all restless temporal paths is known
to be
ΣP
2
-complete [52], that is, the problem is located in the second level of the
polynomial time hierarchy.
Fig. 1 Example of a temporal
graph whose edges are labeled
with time stamps. Bold edges
depict a 2-restless temporal
(s,z)-path. (In general, multiple
time stamps per edge are pos-
sible)
2757
1 3
Algorithmica (2021) 83:2754–2802
1.2 Our Contributions
We introduce the problem
Restless tempoRal path
. To get a finer understanding
of the computational complexity of this problem, we turn our attention to its para-
metrized complexity. In stark contrast to both restless temporal walks and non-rest-
less temporal paths, we show that this problem is NP-hard even in very restricted
settings—in particular, even when the lifetime is restricted to only three time
steps—and W[1]-hard when parameterized by the (vertex deletion) distance to dis-
joint paths of the underlying graph, which implies W[1]-hardness with respect to
many other parameters like feedback vertex number and pathwidth (Sect.3). This is
tight in the sense that the problem can be solved in polynomial time when the under-
lying graph is a forest. On the positive side, we explore parameters of three different
natures. First, we show that the problem is fixed-parameter tractable (FPT) for the
length (in number of hops) of the temporal path (Sect.4). We further show that the
problem is FPT when parameterized by the feedback edge number of the underlying
graph (Sect.5). Additionally, we show that the problem presumably does not admit
a polynomial kernel under the previously mentioned parameterizations where the
problem is in FPT. Our results provide a fine-grained characterization of the trac-
tability boundary of the computation of restless temporal paths for parameters of
the underlying graph, as illustrated by the vicinity of the corresponding parameters
in Fig.2. Then, going beyond parameters related to the output and to the underly-
ing graph, we define a novel temporal version of the classic feedback vertex num-
ber called timed feedback vertex number. Intuitively, it counts the number of vertex
appearances that have to be removed from the temporal graph such that its underly-
ing graph becomes cycle-free. We show that finding restless temporal paths is FPT
when parameterized by this parameter (Sect.6). We believe that the latter is an inter-
esting turn of events compared to our hardness results.
1.3 Strict Versus Non‑strict Temporal Paths
In this paper, we focus mainly on the case of non-strict temporal paths, i.e., the times
along a path are required to be non-decreasing. We expect most of the algorithms
Fig. 2 Relevant part of the hierarchy among classic parameters of the underlying graph
(cf.Sorgeetal.[57]) for our results for
Restless tempoRal path
2758 Algorithmica (2021) 83:2754–2802
1 3
and reductions to be extendable to a strict setting, albeit with some change in the
results themselves. For instance, a similar NP-hardness reduction as for non-strict
temporal paths may apply, but requires more than a constant lifetime to be adapted.
In fact, the length of a strict temporal path is trivially bounded by the lifetime itself,
thus an FPT algorithm for the length parameter implies one for the lifetime param-
eter as well.
2 Preliminaries
Here, we formally introduce the most important concepts related to temporal graphs
and paths, and give the formal problem definition of
(shoRt) Restless tempoRal (
s, z)
-path
.
An interval is an ordered set
[a,b] ∶= {n∣n∈ℕ∧a≤n≤b},
where
.
Further, let
[a] ∶= [1, a]
.
2.1 Static Graphs
We use standard notation from (static) graph theory[24]. Unless stated otherwise,
we assume graphs in this paper to be undirected and simple. To clearly distinguish
them from temporal graphs, they are sometimes referred to as static graphs. Given a
(static) graph
G=(V,E)
with
E
⊆
(
V
2
)
, we denote by
V(G) ∶= V
and
E(G) ∶= E
the
sets of its vertices and edges, respectively.
We call two vertices
u,v∈V
adjacent if
{u,v}∈E
. Two edges
e1,e2∈E
are adjacent if
e1∩e2≠�
. For a vertex
v∈V
, we denote by
degG(v)
the degree
of the vertex, that is,
degG(v)=|{w∈V∣{v,w}∈E}|
. For some vertex subset
V′⊆V
, we denote by
G[V�]
the induced subgraph of G on the vertex set
V′
, that
is,
G[V�]=(V�
,E�)
where
E�= {{v,w}∣{v,w}∈E∧v∈V�∧w∈V�}
. For some
vertex subset
V′⊆V
, we denote by
G−V�
the subgraph of G without the vertices in
V′
, that is,
G−V�=G[V⧵V�]
. For some edge subset
E′⊆E
, we denote by
G−E�
the subgraph of G without the edges
E′
, that is,
G−E�=(V,E⧵E�)
.
An (s, z)-path of length k is a sequence
P= ({s=v0,v1},{v1,v2},…,
{vk−1,vk=z})
of edges such that for all
i∈[k]
we have that
{vi−1,vi}∈E
and
vi≠vj
for all
i,j∈[k]
. We denote
v0
and
vk
as the endpoints ofP. We further denote byE(P)
the set of edges of path P, that is,
E(P) = {{v0,v1},{v1,v2},…,{vk−1,vk}}
and by
V(P) the set of vertices visited by the path, that is,
V
(P)=
⋃e∈E(P)e
. If
v0=vk
and P
is of length at least three, then P is a cycle.
2.2 Temporal Graphs
An (undirected, simple) temporal graph is a tuple
G=(V,E1,…,E𝓁)
(or
G=(V,(Ei)i∈[
𝓁
])
for short), with
E
i⊆
(
V
2)
for all
i∈[𝓁]
. We call
𝓁(G) ∶= 𝓁
the
lifetime of
G
. As with static graphs, we assume all temporal graphs in this paper
to be undirected and simple. We call the graph
Gi(G)=(V,Ei(G))
the layeri of
G
2759
1 3
Algorithmica (2021) 83:2754–2802
where
Ei(G) ∶= Ei
. If
Ei=�
, then
Gi
is a trivial layer. We call layers
Gi
and
Gi+1
consecutive. We call i a time step. If an edge e is present at time i, that is,
e∈Ei
,
we say that e has time stamp i. We further denote
V(G) ∶= V
. The underlying
graph
G↓(G)
of
G
is defined as
G↓
(G)∶=(V,
⋃𝓁(G)
i=1
E
i
(G
))
. To improve readability,
we remove
(G)
from the introduced notations whenever it is clear from the con-
text. For every
v∈V
and every time step
t∈[𝓁]
, we denote the appearance of
vertex v at timet by the pair (v,t). For every
t∈[𝓁]
and every
e∈Et
we call the
pair (e,t) a time edge. For a time edge
({v,w},t)
we call the vertex appearances
(v,t) and (w,t) its endpoints. We assume that the size (for example when refer-
ring to input sizes in running time analyzes) of
G
is
�
G
�
∶=
�
V
�
+
∑𝓁
i=1
min{1,
�
E
i�}
,
that is, we do not assume that we have compact representations of temporal
graphs. Finally, we write n for |V|.
A temporal (s,z)-walk (or temporal walk) of lengthk from vertex
s=v0
to ver-
tex
z=vk
in a temporal graph
G=(V,(Ei)i∈[
𝓁
])
is a sequence
P
=
((
v
i−1
,v
i
,t
i))k
i=1
of triples that we call transitions such that for all
i∈[k]
we have that
{vi−1,vi}∈Eti
and for all
i∈[k−1]
we have that
ti≤ti+1
. Moreover, we call P a
temporal (s,z)-path (or temporal path) of length k if
vi≠vj
for all
i,j∈{0, …,k}
with
i≠j
. Given a temporal path
P
=
((
v
i−1
,v
i
,t
i))k
i=1
, we denote the set of verti-
ces of P by
V(P)={v0,v1,…,vk}
. Moreover, we say that P visits the vertex
vi
at
time t if
t∈[ti,ti+1]
, where
i∈[k−1]
. A restless temporal path is not allowed to
wait an arbitrary amount of time in a vertex, but has to leave any vertex it visits
within the next
𝛥
time steps, for some given value of
𝛥
. Analogously to the non-
restless case, a restless temporal walk may visit a vertex multiple times.
Definition 1 A temporal path (walk)
P
=
((
vi
−
1,vi,ti
))k
i=1
is
𝛥
-restless if
ti≤ti+1≤ti+𝛥
, for all
i∈[k−1]
. We say that P respects the waiting time
𝛥
.
Having this definition at hand, we are ready to define the main decision prob-
lem of this work.
Note the waiting time at the source vertex s is ignored. This is without loss
of generality, since one can add an auxiliary degree one source vertex which is
only in the first layer adjacent to s. We also consider a variant, where we want to
find
𝛥
-restless paths of a certain maximum length. In the
shoRt Restless tempo
-
Ral path
problem, we are additionally given a integer
k∈ℕ
and the question is
whether there is a
𝛥
-restless temporal path of length at most k from s to z in
G
?
Note that
Restless tempoRal path
is the special case of
shoRt Restless tempo
-
Ral path
for
k=|V|−1
and that both problems are in NP.
2760 Algorithmica (2021) 83:2754–2802
1 3
2.3 Parameterized Complexity
We use standard notation and terminology from parameterized complexity the-
ory[23] and give here a brief overview of the most important concepts that are used
in this paper. A parameterized problem is a language
L⊆Σ∗×ℕ
, where
Σ
is a finite
alphabet. We call the second component the parameter of the problem. A param-
eterized problem is fixed-parameter tractable (in the complexity class FPT) if there
is an algorithm that solves each instance(I,r) in
f(r)
⋅
|I|O(1)
time, for some comput-
able function f. A decidable parameterized problem L admits a polynomial kernel
if there is a polynomial-time algorithm that transforms each instance (I,r) into an
instance
(I�
,r�)
such that
(I,r)∈L
if and only if
(I�
,r�)∈L
and
|(I�,r�)|∈rO(1)
. If a
parameterized problem is hard for the parameterized complexity class W[1], then it
is (presumably) not inFPT. The complexity classes W[1] is closed under parameter-
ized reductions, which may run in FPT-time and additionally set the new parameter
to a value that exclusively depends on the old parameter.
2.4 Basic Observations
If there is a
𝛥
-restless temporal
(s,z)
-path
((
vi
−
1,vi,ti
))k
i=1
in a temporal graph
G
,
then
(
{v
0
,v
1
},…,{v
k−1
,v
k
}
)
is an (s,z)-path in the underlying graph
G↓
. The other
direction does not necessarily hold. However, we now show that for any (s,z)-path
in
G↓
we can decide in linear time whether this path is the support of a
𝛥
-restless
temporal
(s,z)
-path in
G
. As a consequence, we can decide
Restless tempoRal
path
in linear time for any temporal graph where there exists a unique (s,z)-path in
the underlying graph, in particular, if the underlying graph is a forest.
Lemma 1 Let
G=(V,(Ei)i∈[
𝓁
])
be a temporal graph where the underlying graph
G↓
is an(s,z)-path with
s,z∈V
. Then there is an algorithm which computes in
O(|G|)
time the set
Proof Let
V(G↓)={s=v0,…,vn=z}
be the vertices and
E(G↓)={e1={v0,v1},
…,
e
n={
v
n−1,
v
n}}
be the edges of the underlying path. We further define
Li
as the
set of layers of
G
in which the edge
ei∈E(G↓)
exists, that is,
Li∶= {
t
∣
e
i∈
E
t}
.
In the following, we construct a dynamic program on the path. We compute
for every vertex
vi
the table entry
T[vi]
which is defined as the set of all layerst
such that there exists a
𝛥
-restless temporal
(s,vi)
-path with arrival timet. It holds
that
T[v1]=L1
. Then, for all
i∈[2, 𝓁]
, we compute the table entry
T[vi]
by check-
ing for each layer
t∈Li
whether there exists a
𝛥
-restless temporal
(s,vi−1)
-path that
arrives in a layer
t�∈
T
[
v
i−1]
such that we can extend the path to the vertex
vi
in
layert without exceeding the maximum waiting time
𝛥
, that is,
0≤t−t�≤𝛥
. For-
mally, we have
A={
t
∣there is a
𝛥
-restless temporal(
s
,
z
)with arrival time
t
}.
2761
1 3
Algorithmica (2021) 83:2754–2802
It is easy to verify that
T[vi]
contains all layerst such that there exists a
𝛥
-restless
temporal
(s,vi)
-path with arrival timet. After computing the last entry
T[vn]
, this
entry contains the set
A
of all layers t such that there exists a
𝛥
-restless tempo-
ral
(s,z)
-path with arrival timet.
In order to compute a table entries
T[vi]
in linear time, we will need sorted lists
of layers for
Li
and
T[vi−1]
in ascending order. The sorted lists
Li
of layers can be
computed in
O(|G|)
: For every
t∈[𝓁]
, we iterate over each
ei∈Et
and add t to
Li
.
Now assume that
Li
and
T[vi−1]
are lists of layers both in ascending order, then we
can compute the table entry
T[vi]
in
O(|T[vi−1]|+|Li|)
time as follows. Let
T[vi]
be
initially empty. Let t be the first element in
Li
and let
t′
be the first element in
T[vi−1]
:
1. If
t′>t
, then replace t with the next layer in
Li
and repeat.
2. If
t−t�≤𝛥
, then add t to
T[vi]
, replace t with the next layer in
Li
and repeat.
3. Else, replace
t′
with the next layer in
T[vi−1]
and repeat.
This is done until all elements in one of the lists are processed.
The resulting list
T[vi]
is again sorted. Due to this and
T[v1](= L1)
being sorted,
we can assume that
T[vi−1]
is given as a sorted list of layers when computing
T[vi]
.
Hence, we can compute each table entry
T[vi]
in
O(|T[vi−1]|+|Li|)
time. It further
holds that
|T[vi]|≤|Li|
and
∑n
i=1�
L
i�
=
∑𝓁
i=1�
E
i�
. Hence, the dynamic program runs
in
O(|G|)
time.
◻
Furthermore, it is easy to observe that computational hardness of
Restless
tempoRal path
for some fixed value of
𝛥
implies hardness for all larger finite val-
ues of
𝛥
. This allows us to construct hardness reductions for small fixed values of
𝛥
and still obtain general hardness results.
Observation 1 Given an instance
I=(G,s,z,k,𝛥)
of
shoRt Restless tempo
-
Ral path
, we can construct in linear time an instance
I�=(G�,s,z,k,𝛥+1)
of
shoRt Restless tempoRal path
such that I is a yes-instance if and only if
I′
is a
yes-instance.
Proof The result immediately follows from the observation that a temporal graph
G
contains a
𝛥
-restless temporal
(s,z)
-path if and only if the temporal graph
G′
contains
a
(𝛥+1)
-restless temporal
(s,z)
-path, where
G′
is obtained from
G
by inserting one
trivial (edgeless) layer after every
𝛥
consecutive layers.
◻
However, for some special values of
𝛥
we can solve
Restless tempoRal path
in polynomial time.
T[
v
i]∶={
t
∈
L
i∣there is a
t
�∈
T
[
v
i−1]with 0 ≤
t
−
t
�≤𝛥}.
2762 Algorithmica (2021) 83:2754–2802
1 3
Observation 2
Restless tempoRal path
on instances
(G,s,z,𝛥)
can be solved in
polynomial time, if
𝛥=0
or
𝛥≥𝓁
.
Proof Considering
𝛥=0
implies that the entirety of a path between s and z must be
realized in a single layer. Thus, the problem is equivalent to testing if at least one of
the layers
Gi
contains a (static) path between s and z.
◻
If
𝛥≥𝓁
, then
𝛥
-restless temporal paths correspond to unrestricted temporal
paths, whose computation can be made using any of the (polynomial time) algo-
rithms inBui-Xuan etal.[17].
3 Hardness Results forRestless Temporal Paths
In this section we present a thorough analysis of the computational hardness of
Restless tempoRal path
which also transfers to
shoRt Restless tempoRal path
.
3.1 NP‑hardness forfew layers
We start by showing that
Restless tempoRal path
is NP-complete even if the life-
time of the input temporal graph is constant. The reduction is similar in spirit to the
classic NP-hardness reduction for
2-Disjoint paths
in directed graphs by Fortune
etal.[33].
Theorem1
Restless tempoRal path
is NP-complete for all finite
𝛥≥1
and
𝓁≥𝛥+2
even if every edge has only one time stamp.
Proof We show this result by a reduction from the NP-complete
exact
(3, 4)
-sat
problem[59]. The problem
exact
(3, 4)
-sat asks whether a formula
𝜙
is satisfiable,
assuming that it is given in conjunctive normal form, each clause having exactly
three literals and each variable appearing in exactly four clauses.
Let
𝜙
be an instance of
exact
(3, 4)
-sat with n variables and m clauses. We con-
struct a temporal graph
G=(V,(Ei)i∈[
𝓁
])
with
𝓁=3
consisting of a series of variable
gadgets followed by dedicated vertices
sn
and
s′
and then a series of clause gadg-
ets. It is constructed in such a way that for
𝛥=1
, any
𝛥
-restless temporal (s,z)-path
has to visit a vertex
sn
and each possible
𝛥
-restless temporal
(s,sn)
-path represents
exactly one variable assignment for the formula
𝜙
. Further we show that for any
𝛥
-restless temporal
(s,sn)
-path it holds that it can be extended to a
𝛥
-restless temporal
(s,z)-path if and only if the
𝛥
-restless temporal
(s,sn)
-path represents a satisfying
assignment for the formula
𝜙
.
Variable Gadget. We start by adding a vertex s to the vertex set V of
G
. For each
variable
xi
with
i∈[n]
of
𝜙
, we add 9 fresh vertices to V:
x(1)
i
,
x(2)
i
,
x(3)
i
, x
(4)
i
, x
(1)
i
,
2763
1 3
Algorithmica (2021) 83:2754–2802
x(2)
i
,
x(3)
i
,
x(4)
i
, and
si
. Each variable
xi
is represented by a gadget consisting two dis-
joint path segments of four vertices each. One path segment is formed by
x(1)
i
, x
(2)
i
,
x(3)
i
, and
x(4)
i
in that order and the second path segment is formed by
x(1)
i
,
x(2)
i
, x
(3)
i
,
and
x(4)
i
in that order. The connecting edges all appear exclusively at time step one,
that is,
{
x
(1)
i
,x
(2)
i}
,
{
x
(2)
i
,x
(3)
i}
, and
{
x
(3)
i
,x
(4)
i}
are added to
E1
. Analogously for the
edges connecting x
(1)
i
, x
(2)
i
, x
(3)
i
, and
x(4)
i
. Intuitively, if a
𝛥
-restless temporal (s,z)-
path passes the first segment, then this corresponds to setting the variable
xi
to false.
If it passes the second segment, then the variable is set to true. For all
i∈[n−1]
we
add the edges
{
x
(4)
i
,s
i}
,
{
x
(4)
i
,s
i}
,
{
s
i
,x
(1)
i+1}
, and
{
s
i
,x
(1)
i+1}
to
E1
and, additionally, we
add
{
s,x
(1)
1}
,
{
s,x
(1)
1}
,
{
x
(4)
n
,s
n}
, and
{
x
(4)
n
,s
n}
to
E1
.
We can observe that there are exactly
2n
different temporal
(s,sn)
-paths at time
stepone. Intuitively, each path represents exactly one variable assignment for the
formula
𝜙
.
Clause Gadget. We add a vertex z to V. For each clause
cj
with
j∈[m]
we add a
fresh vertex
cj
to V. We further add a vertex
s′
to V and add the edge
{sn,s�}
to
E2
.
Let
xi
(or
xi
) be a literal that appears in clause
cj
and let this be the kth appearance of
variable
xi
in
𝜙
. Then, we add the edges
{
c
j
,x
(k)
i
},{x
(k)
i
,c
j+1}
(or
{
c
j
,x
(k)
i
},{x
(k)
i
,c
j+1}
)
to
E3
(where
cm+1=z
). Finally, we add the edge
{s�,c1}
to
E3
.
Hence, there are exactly
3m
different temporal
(s�
,z)
-paths at time stepthree. Each
path must visit the clause vertices
c1,…,cm
in the given order by construction.
Finally, we set
𝛥=1
. This finishes the construction, for a visualization see Fig.3.
It is easy to check that every edge in the constructed temporal graph has only one
time step and that the temporal graph can be computed in polynomial time.
Correctness. Now we can show that
𝜙
is satisfiable if and only if
G
has a
𝛥
-rest-
less temporal (s,z)-path.
(⇒)
: Let us assume there is a satisfying assignment for formula
𝜙
. Then we con-
struct a
𝛥
-restless temporal path from vertex s to z as follows. Starting from s, for
Fig. 3 Illustration of the temporal graph constructed by the reduction in the proof of Theorem 1. An
excerpt is shown with variable gadgets for
x1
,
x2
, and
x3
and the clause gadget for
ci=(x1∨x2∨¬x3)
,
where
x1
appears for the fourth time,
x2
appears for the third time, and
x3
also appears for the third time.
Black edges appear at time step one, the blue (dotted) edge
{sn
,
s�}
appears at time step two, and the red
(dashed) edges appear at time step three
2764 Algorithmica (2021) 83:2754–2802
1 3
each variable
xi
of
𝜙
the
𝛥
-restless temporal path passes through the variables x
(1)
i
,
x(2)
i
,
x(3)
i
, and x
(4)
i
, if
xi
is set to false, and x
(1)
i
,
x(2)
i
,
x(3)
i
, and
x(4)
i
, if
xi
is set to true, at
time step one. The
𝛥
-restless temporal path arrives at time step one in the vertex
sn
.
In time step two it goes from
sn
to
s′
.
At time step three, the
𝛥
-restless temporal path can be extended to
c1
. In each
clause
cj
for
j∈[m]
there is at least one literal
xi
(or
xi
) that is evaluated to true.
Let
cj
be the kth clause in which
xi
appears. We have that, depending on whether
xi
is
set to true (or false), the vertex
x(k)
i
(or
x(k)
i
) has not been visited so far. Hence, the
𝛥
-restless temporal path can be extended from
cj
to
cj+1
(or toz for
j=m
) at time step
three via
x(k)
i
(or
x(k)
i
). Thus, there exists a
𝛥
-restless temporal(s,z)-path in
G
.
(⇐)
: Let us assume that there exists a
𝛥
-restless temporal (s,z)-path in the con-
structed temporal graph
G
. Note that any
𝛥
-restless temporal (s,z)-path must reach
sn
in time stepone because the variable gadget has only edges at time stepone and
the waiting time
𝛥=1
prevents the path to enter the clause gadget (which only has
edges at time step three) before using the edge
{sn,s�}
at time step two.
It is easy to see that for the first part of the
𝛥
-restless temporal graph from s to
sn
it holds that for each
i∈[n]
, it visits either vertices
x(1)
i
,
x(2)
i
,
x(3)
i
, and
x(4)
i
, or vertices
x(1)
i
,
x(2)
i
, x
(3)
i
, and x
(4)
i
. In the former case we set
xi
to false and in the latter case we
set
xi
to true. We claim that this produces a satisfying assignment for
𝜙
.
In time stepthree, the part of the
𝛥
-restless temporal path from
s′
toz has to pass
vertices
c1,c2,…,cm
to reachz. The
𝛥
-restless temporal path passes exactly one var-
iable vertex
x(k)
i
(or
x(k)
i
) when going from
cj
to
cj+1
(and finally from
cm
toz) that has
not been visited so far and that corresponds to a variable that appears in the clause
cj
for the kth time. The fact that the variable vertex was not visited implies that we set
the corresponding variable to a truth value that makes it satisfy clause
cj
. This holds
for all
j∈[m]
. Hence, each clause is satisfied by the constructed assignment and,
consequently,
𝜙
is satisfiable.
◻
The reduction used in the proof of Theorem1 also yields a running time lower
bound assuming the Exponential Time Hypothesis (ETH)[40, 41].
Corollary 1
Restless tempoRal path
does not admit a
f(
𝓁
)o(|G|)
-time algorithm for
any computable functionf unless the ETH fails.
Proof First, note that any 3-sat formula with m clauses can be transformed into an
equisatisfiable
exact
(3, 4)
-sat formula with O(m) clauses[59]. The reduction pre-
sented in the proof of Theorem1 produces an instance of
Restless tempoRal path
with a temporal graph of size
|G|=O(m)
and
𝓁=3
. Hence an algorithm for
Rest
-
less tempoRal path
with running time
f(
𝓁
)o(|G|)
for some computable function f
would imply the existence of an
2o(m)
-time algorithm for 3-sat. This is a contradic-
tion to the ETH[40, 41].
◻
2765
1 3
Algorithmica (2021) 83:2754–2802
Furthermore, the reduction behind Theorem 1 can be modified such that
it also yields that
Restless tempoRal path
is NP-hard, even if the underlying
graph has constant maximum degree or the underlying graph is a clique where
one edge (
{s,z})
is missing. Note that in the latter case the underlying graph con-
tains all edges except the one edge which would turn the instance into a trivial
yes-instance.
Corollary 2
Restless tempoRal path
is NP-hard, even if the underlying graph has all
but one edge or maximum degree six.
Proof That
Restless tempoRal path
is NP-hard, even if the underlying graph has
maximum degree six follows directly from the construction used in the proof of The-
orem1. To show that that
Restless tempoRal path
is NP-hard, even if the underly-
ing graph has all edges except
{s,z}
, we reduce from
Restless tempoRal path
. Let
I=(G=(V,(Ei)i∈[
𝓁
]),s,z,𝛥)
be an instance of
Restless tempoRal path
with
𝓁=3
.
We construct an instance
I�
∶= (
G�
=(V,E
�
1
,E
�
2
,E
�
3
,E
�
4
,E
�
5
),s,z,
𝛥)
of
Restless tem
-
poRal path
, where
E
�
1
=
(V⧵{s}
2)
,
E�
2
∶= E
1
,
E�
3
∶= E
2
,
E�
4
∶= E
3
, and
E
�
5
=
(V⧵{z}
2)
.
Observe that none of the edges in
E1∪E5
can be used in temporal (s,z)-path. Hence,
I is a yes-instance if and only if
I′
is a yes-instance. Furthermore,
E1∪E5
contain all
possible edges except
{s,z}
.
◻
3.2 W[1]‑Hardness forDistance toDisjoint Paths
In the following, we show that parameterizing
Restless tempoRal path
with struc-
tural graph parameters of the underlying graph of the input temporal graph pre-
sumably does not yield fixed-parameter tractability for a large number of popular
parameters. In particular, we show that
Restless tempoRal path
parameterized by
the distance to disjoint paths of the underlying graph is W[1]-hard. The distance to
disjoint paths of a graph G is the minimum number of vertices we have to remove
from G such that the reminder of G is a set of disjoint paths. Many well-known
graph parameters can be upper-bounded in the distance to disjoint paths, e.g.,path-
width, treewidth, and feedback vertex number [57]. Hence, the following theorem
also implies that
Restless tempoRal path
is W[1]-hard when parameterized by the
pathwidth or the feedback vertex number of the underlying graph.
Theorem2
Restless tempoRal path
parameterized by the distance to disjoint path of
the underlying graph is W[1] -hard for all
𝛥≥1
even if every edge has only one time
stamp.
Proof We present a parameterized reduction from
multicoloReD clique
where,
given a k-partite graph
H=(U1⊎U2⊎…⊎Uk,F)
, we are asked to decide whether
H contains a clique of size k.
multicoloReD clique
is known to be W[1]-hard when
parameterized by the clique size k[23, 28].
2766 Algorithmica (2021) 83:2754–2802
1 3
Let
(H=(U1⊎U2⊎…⊎Uk,F),k)
be an instance of
multicoloReD clique
. For
each
i,j∈[k]
with
i<j
let
Fi,j= {{u,v}∈F∣u∈Ui∧v∈Uj}
be the set of edges
between vertices in
Ui
and
Uj
. We can assume that
k≥3
, otherwise we can solve
the instance in polynomial time. Without loss of generality, we assume that for all
i,j,i�
,j�∈[k]
with
i<j
and
i′<j′
we have that
|Fi,j|=|Fi
�
,j
�
|=m
for some
m∈ℕ
.
Note that if this is not the case, we add new vertices and single edges to increase the
cardinality of some set
Fi,j
and this does not introduce new cliques since
k≥3
. We
further assume without loss of generality that
|U1|=|U2|=⋯=|Uk|=n
for some
n∈ℕ
. If this is not the case, we can add additional isolated vertices to increase the
cardinality of some set
Ui
. We construct a temporal graph
G=(V,(Ei)i∈[
𝓁
])
with two
distinct vertices
s,z∈V
such that there is a
𝛥
-restless temporal
(s,z)
-path in
G
if
and only ifH contains a clique of size k. Furthermore, we show that the underlying
graph
G↓
of
G
has a distance to disjoint paths of
O(k2)
.
Vertex Selection Gadgets. For each set
Ui
with
i∈[k]
of the vertex set of H we
create the following gadget. Let
Ui
={u
(i)
1
,u
(i)
2
,…,u(i)
n}
. We create a path of length
k⋅n+n+1
on fresh vertices
w(i)
1
,v
(i)
1,1
,v
(i)
1,2
,…,v
(i)
1,k
,w
(i)
2
,v
(i)
2,1
,…,v
(i)
n,k
,w
(i)
n+1
. Intui-
tively, this path contains a segment of length k for each vertex in
Ui
which are sepa-
rated by the vertices
w(i)
j
, and the construction will allow a
𝛥
-restless temporal
(s,z)
-
path to skip exactly one of these segments, which is going to correspond to selecting
this vertex for the clique.
Formally, for each vertex
u(i)
j
∈U
i
we create k vertices
v(i)
j,1
,v
(i)
j,2
,…,v
(i)
j,k
, which we
call the segment corresponding to
u(i)
j
. We further create vertices
w(i)
1
,w
(i)
2
,…,w
(i)
n+1
.
For all
j∈[n]
and
x∈[k−1]
we connect vertices
v(i)
j,x
and
v(i)
j,x+1
with an edge at time
(i−1)⋅n+j
and we connect
w(i)
j
with
v(i)
j,1
and
w(i)
j+1
with
v(i)
j,k
at time
(i−1)⋅n+j
each.
Lastly, we introduce a “skip vertex”
s(i)
that will allow a
𝛥
-restless temporal
(s,z)
-
path to skip one path segment of length k that corresponds to one of the vertices
in
Ui
. For each
j∈[n+1]
, we connect vertices
s(i)
and
w(i)
j
with an edge at time
(i−1)⋅n+j
.
Now we connect the gadgets for all
Ui
’s in sequence, that is, a
𝛥
-restless tempo-
ral
(s,z)
-path passes through the gadgets one after another, selecting one vertex of
each part
Ui
. Formally, for all
i∈[k−1]
, we connect vertices
w(i)
n+1
and
w(i+1)
1
with
an edge at time
i⋅n+1
. It is easy to check that after the removal of the vertices
{s(1),s(2),…,s(k)}
, the vertex selection gadget is a path. The vertex selection gadget
is visualized in Fig.4.
Validation Gadgets. A
𝛥
-restless temporal
(s,z)
-path has to pass through the val-
idation gadgets after it passed through the vertex selection gadgets. Here, we are
forced to choose a point in time where we visit two vertices of two different vertex
selection gadgets. This choice corresponds to the selection of an edge. Intuitively,
2767
1 3
Algorithmica (2021) 83:2754–2802
this should only be possible if the selected vertices form a clique. We construct the
gadget in the following way.
For each
i,j∈[k]
with
i<j
let the edges in
Fi,j
be ordered in an arbitrary way,
that is,
Fi,j
={e
(i,j)
1
,e
(i,j)
2
,…,e
(i,j)
m
}
. We create two paths of length 2m on fresh verti-
ces
v(i,j)
1,1
,v
(i,j)
1,2
,v
(i,j)
2,1 ,
v(i,j)
2,2
,…,v
(i,j)
m,2
and
v(i,j)
1,3
,v
(i,j)
1,4
,v
(i,j)
2,3
,v
(i,j)
2,4
,…,v
(i,j)
m,4
, respectively. Intui-
tively, the first path selects an edge from
Ui
to
Uj
and the transition to the second
path should only be possible if the two endpoints of the selected edge are selected in
the corresponding vertex selection gadgets.
Formally, for each edge
e(i,j)
h
∈F
i,j
we create four vertices
v(i,j)
h,1
,v
(i,j)
h,2
,v
(i,j)
h,3
,v
(i,j)
h,4
. Fur-
thermore, we introduce three extra vertices
s(i,j)
1
,s
(i,j)
2
,s
(i,j)
3
. For all
h∈[m]
we connect
vertices
v(i,j)
h,1
and
v(i,j)
h,2
with an edge at time
yi,j+2h−1
, we connect vertices
v(i,j)
h,1
and
s(i,j)
1
with an edge at time
yi,j+2h−1
, we connect vertices
v(i,j)
h,3
and
v(i,j)
h,4
with an
edge at time
yi,j+2h−1
, we connect vertices
v(i,j)
h,3
and
s(i,j)
3
with an edge at time
yi,j+2h−1
, and if
h<m
, we connect vertices
v(i,j)
h,2
and
v(i,j)
h+1,1
with an edge at time
yi,j+2h
and we connect vertices
v(i,j)
h,4
and
v(i,j)
h+1,3
with an edge at time
yi,j+2h
, where
y
i,j=k⋅n+2m⋅(i⋅j+
1
2
⋅i⋅(i−1)−1
)
(the value of
yi,j
can be interpreted as a
“time offset” for the validation gadget for
Fi,j
, the value is computed by adding all
time steps needed in validation gadget for
Fi
′
,j′
with
i′<j′
,
i′≤i
,
j′≤j
, and
(i�
,j�)≠(i,j)
). Next, for each edge
e(i,j)
h
={u(i)
a
,u
(j)
b
}∈F
i,j
we connect vertices
s(i,j)
1
and
v(i)
a,j
(from the vertex selection gadget for
Ui
) with an edge at time
yi,j+2h−1
,
we connect vertices
s(i,j)
2
and
v(i)
a,j
with an edge at time
yi,j+2h−1
, we connect verti-
ces
s(i,j)
2
and
v(j)
b,i
(from the vertex selection gadget for
Uj
) with an edge at time
yi,j+2
h
−1
, and we connect vertices
s(i,j)
3
and
v(j)
b,i
with an edge at time
yi,j+2
h
−1
.
Intuitively, the time labels on the edges and the waiting time restrictions enforce
that when arriving at
s(i,j)
1
there is only one way to continue to
s(i,j)
2
for which is it nec-
essary to visit a vertex in the vertex selection gadget that corresponds to an endpoint
Fig. 4 Visualization of the vertex selection gadget for
U1
from the reduction of Theorem2. Black edges
appear at time step one, red edges (densely dashed) at time step two, blue edges (dashdotted) at time step
three, green edges (dotted) at time step
n−1
, and orange edges (loosely dashed) at time step n. For the
segment corresponding to
u(1)
1
∈U
1
all vertex names are presented, for the other segments the names are
analogous but omitted. The auxiliary
w(1)
1
,…,w(1)
n
,
…
vertices are colored gray. The “skip vertex”
s(1)
is
depicted as a yellow square. Note that after the removal of
s(1)
the vertex selection gadget for
U1
is a path
2768 Algorithmica (2021) 83:2754–2802
1 3
of the selected edge. Similarly, from
s(i,j)
2
there is only one way to continue to
s(i,j)
3
for
which it is necessary to visit a vertex in the vertex selection gadget that corresponds
to the other endpoint of the selected edge. For a visualization of the validation
gadget see Fig.5, where the red dashed path corresponds to the selection of an edge.
Now we connect the gadgets for all
Fi,j
’s in sequence, that is, a
𝛥
-restless tempo-
ral
(s,z)
-path passes through the gadgets one after another, selecting one edge of each
part
Fi,j
of the edge set F. Formally, for each
i,j∈[k]
with
i<j
, if
i<j−1
, we
connect vertices
v(i,j)
m,4
and
v(i+1,j)
1,1
with an edge at time
yi+1,j
, and if
i=j−1<k−1
, we
connect vertices
v(i,j)
m,4
and
v(i,j+1)
1,1
with an edge at time
yi,j+1
. It is easy to check that after
the removal of
3
⋅
(
k
2
)
many vertices
{
s
(1,2)
1
,s
(1,2)
2
,s
(1,2)
3
,s
(1,3)
1
,…,s
(1,
k
)
3
,…s
(
k
−1,
k
)
3}
, the
validation gadgets are a set of disjoint paths, see Fig.5.
Finally, we create two new vertices s and z, we connect vertices s and
w(1)
1
(the
“first” vertex of the vertex selection gadgets) with an edge at time one, we connect
vertices s and
s(1)
(the “skip vertex” of the first vertex selection gadget) with an edge
at time one, and we connect z and
v(k−1,k)
m,4
(the “last” vertex of the validation gadgets)
Fig. 5 Visualization of the validation gadget for
Fi,j
from the reduction of Theorem2. The “first path” of
the gadget is depicted vertically on the left, the “second path” on the right. The connections to the vertex
selection gadgets for the edge
e(i,j)
h
={u(i)
a
,u
(j)
b
}∈F
i,j
are depicted. The edges in red (dashed) correspond
to the path through the gadget if edge
e(i,j)
h
is “selected” and all these edges have the same time stamp.
The vertex selection gadgets corresponding to
Ui
and
Uj
are depicted as triangles in the upper center part.
The three vertices
s(i,j)
1
,
s(i,j)
2
, and
s(i,j)
3
are colored yellow (squared). Note that after the removal of
s(i,j)
1
,
s(i,j)
2
,
and
s(i,j)
3
, the validation gadget for
Fi,j
is a set of disjoint paths
2769
1 3
Algorithmica (2021) 83:2754–2802
with an edge at time
k
⋅
n+m
⋅
(3k2+5k+3)
. We further connect vertices
w(k)
n+1
and
v(1,2)
1,1
(connecting the vertex selection gadgets and the validation gadgets) with
an edge at time
k⋅n
. Finally, we set
𝛥=1
. This completes the construction. It is easy
to check that
G
can be constructed in polynomial time and that the distance to disjoint
paths of
G↓
is at most
k
+3⋅
(
k
2
)
and that every edge has only one time stamp.
Correctness. Now we show that H contains a clique of size k if and only if there
is a
𝛥
-restless temporal path from s to z in
G
.
(⇒)
: Assume that H contains a clique of size k and let
X⊆V(H)
with
|X|=k
be
the set of vertices that form the clique in H. Now we show how to construct a
𝛥
-rest-
less temporal
(s,z)
-path in
G
. Note that since H is k-partite, we have that
|Ui∩X|=1
for all
i∈[k]
. The temporal path starts at vertex s in
G
and then first passes
through the vertex selection gadgets. If
u(i)
j
∈
X
for some
i∈[k]
and
j∈[n]
,
then the temporal path skips the segment corresponding to
u(i)
j
in the vertex selection
gadget for
Ui
. More formally, the temporal path follows the vertices
w(i)
1
,v
(i)
1,1
,v
(i)
1,2
,…,v
(i)
1,k
,w
(i)
2
,…,v
(i)
j−1,k
,w
(i)
j,
s
(i),w
(i)
j+1
,v
(i)
j+1,1
,…,v
(i)
n,k
,w
(i)
n+1
in that order,
that is, the path skips vertices
v(i)
j,1
,v
(i)
j,2
,…,v
(i)
j,k
. It is easy to check that the time labels
of the edges in the vertex selection gadget allow for a restless temporal path as
described that respects the waiting time
𝛥
.
In the validation gadget for
Fi,j
with
i<j
, the path “selects” the edge
(Ui∩X)∪(Uj∩X)∈Fi,j
that connects the vertices from the parts
Ui
and
Uj
that are
contained in the clique X. Let
(
U
i
∩X)∪(U
j
∩X)={u(i)
a
,u
(j)
b
}=e
(i,j)
h
∈F
i,j
. For-
mally, the path follows vertices
v(i,j)
1,1
,v
(i,j)
1,2
,v
(i,j)
2,1
,v
(i,j)
2,2
,…,v
(i,j)
h,1
,s
(i,j)
1
,v
(i)
a,j,
s(i,j)
2
,v
(j)
b,i
,s
(i,j)
3
,v
(i,j)
h,4
,v
(i,j)
h+1,3
,v
(i,j)
h+1,4
,…,v
(i,j)
m,4
in that order. Note that vertices
v(i)
a,j
and
v(j)
b,i
have not been used by the path in the vertex selection gadgets, since they appear in
the segments that were skipped by the temporal path in the corresponding vertex
selection gadgets. Furthermore, since the clique inH only contains one edge that
connects vertices from
Ui
and
Uj
, the vertices
v(i)
a,j
and
v(j)
b,i
have not been used by the
temporal path in an earlier validation gadget. It is easy to check that the time labels
of the edges in the validation gadget allow for a
𝛥
-restless temporal path as
described. After the last validation gadget the path arrives at vertexz. Hence, we
have found a
𝛥
-restless temporal
(s,z)
-path in
G
.
(⇐)
: Assume that we are given a
𝛥
-restless temporal
(s,z)
-path in
G
. We now
show that H contains a clique of size k.
After starting at s, the
𝛥
-restless temporal path first passes the vertex selection
gadgets. Here, we need to make the important observation, that for each
i∈[k]
, any
𝛥
-restless temporal
(s,z)
-path has to “skip” at least one segment corresponding to
one vertex
u(i)
j
∈U
i
in the vertex selection gadget corresponding to
Ui
, otherwise the
temporal path cannot traverse the validation gadgets. More formally, assume for
contradiction that there is a
𝛥
-restless temporal
(s,z)
-path and an
i∈[k]
such that the
2770 Algorithmica (2021) 83:2754–2802
1 3
temporal path visits all vertices in the vertex selection gadget corresponding to
Ui
.
Let
j∈[k]
with
j≠i
. Assume that
i<j
(the other case works analogously). We
claim that the temporal path cannot traverse the validation gadget for
Fi,j
. For the
temporal path to go from
s(i,j)
1
to
s(i,j)
2
by construction it has to visit at least one vertex
from the vertex selection gadget for
Ui
. If all vertices have already been visited, that
would mean the
𝛥
-restless temporal
(s,z)
-path visits one vertex twice—a
contradiction.
The waiting time
𝛥
prevents the temporal path from “skipping” more than one
segment. More formally, any
𝛥
-restless temporal
(s,z)
-path arrives at the “skip ver-
tex”
s(i)
of the vertex selection gadget for
Ui
at time
(i−1)⋅n+j
, for some
j∈[k−1]
. By construction this means the path visits
w(i)
j
, then
s(i)
, and then has to
continue with
w(i)
j+1
since there is only one time edge the path can use without violat-
ing the waiting time
𝛥
. It follows that the temporal path skips exactly the segment
corresponding to
u(i)
j
∈U
i
.
This implies that any
𝛥
-restless temporal
(s,z)
-path that traverses the vertex selec-
tion gadgets leaves exactly one segment of every vertex selection gadget unvisited.
Let the set
X
={u
(i)
j
∈Ui∣i∈[k]∧j∈[n]∧vj,1 is an unvisited vertex.
}
be the set
of vertices corresponding to the segments that are “skipped” by the given
𝛥
-restless
temporal
(s,z)
-path. It is easy to check that
|X|=k
. We claim that X is a clique in H.
Assume for contradiction that it is not. Then there are two vertices
u(
i
)
i
�,u
(j)
j
�∈X
such that the edge
{
u
(i)
i
�,u
(j)
j
�
}
is not in F. Assume that
i<j
. We show that then the
𝛥
-restless temporal
(s,z)
-path is not able to pass through the validation gadget for
Fi,j
.
By assumption we have that
{
u
(i)
i
�,u
(j)
j
�}∉Fi,
j
. Note that the validation gadget is
designed in a way that the first path “selects” an edge from
Fi,j
and then the waiting
time of one enforces that a
𝛥
-restless temporal
(s,z)
-path can only move from the
first path to the second path of a validation gadget if the two endpoints of the
selected edge are vertices whose corresponding segments in the vertex selection
gadget were skipped. We have seen that for every
Ui
with
i∈[k]
, the path segment
corresponding to exactly one vertex of that set was skipped. Since
{
u
(i)
i
�,u
(j)
j
�}∉Fi,
j
,
we have that for every edge in
Fi,j
that the segment corresponding to at least one of
the two endpoints of the edge was not skipped. Hence, we have that the
𝛥
-restless
temporal path cannot pass through the validation gadget of
Fi,j
and cannot reachz—a
contradiction.
◻
4 An FPT‑Algorithm forShort Restless Temporal Path
In this section, we discuss how to find short restless temporal paths. Recall that in
shoRt Restless tempoRal path
, we are given an additional integer k as input and
are asked whether there exists a
𝛥
-restless temporal
(s,z)
-path that uses at most k
2771
1 3
Algorithmica (2021) 83:2754–2802
time edges. By Theorem1 this problem is NP-hard. Note that in the contact tracing
scenario from the beginning, we can expect to have a small k and a large temporal
graph.
Theorem3
shoRt Restless tempoRal path
is
(i) solvable in
2k
⋅
|G|O(1)
time with a constant one-side error,3
(ii) deterministically solvable in
2O(k)
⋅
|G|𝛥
time,
Note that we can solve
shoRt Restless tempoRal path
such that the running
time is independent from the lifetime
𝓁
of the temporal graph. To show Theorem3,
we first reduce the problem to a specific path problem in directed graphs. Then, we
apply known algebraic tools for multilinear monomials detection. Here, Theorem3
(i) is based on Williams [60]. To get a deterministic algorithm with a running time
almost linear in
|G|
, we show a different approach based on representative sets [31]
which results in Theorem3 (ii).
Reduction to directed graphs. We introduce a so-called
𝛥
-(s,z)-expansion for two
vertices s and z of a temporal graph with waiting times. That is, a time-expanded
version of the temporal graph which reduces reachability questions to directed
graphs. While similar approaches have been applied several times [4, 12, 50, 61,
62], to the best of our knowledge, this is the first time that waiting-times are con-
sidered. In a nutshell, the
𝛥
-(s,z)-expansion has for each vertex v at most
𝓁
many
copies
v1,…,v𝓁
and if an
(s,z)
-dipath visits
vi
, it means that the corresponding
𝛥
-restless temporal
(s,z)
-walk visits v at time i.
Definition 2 (
𝛥
-(s,z)-Expansion) Let
G=(V,(Ei)i∈[
𝓁
])
be a temporal graph with two
distinct vertices
s,z∈V
such that
{s,z}∉Et
, for all
t∈[𝓁]
. Let
𝛥≤𝓁
. The
𝛥
-(s,z)-
expansion of
G
is the directed graph
D=(V�
,E�)
with
(i)
V�
∶= {s,z}∪
{
v
t|
v∈e,e∈E
t
,v∉{s,z}
}
,
(ii)
Es
∶=
{
(s,v
t
)
|
{s,v}∈E
t}
,
(iii)
Ez
∶=
{
(v
i
,z)
|
v
i
∈V
�
,{v,z}∈E
t
,0
≤
t−i
≤
𝛥
}
, and
(iv)
E�
∶= E
s
∪E
z
∪
{
(v
i
,w
t
)
|
v
i
∈V
�
⧵{s,z},{v,w}∈E
t
,0
≤
t−i
≤
𝛥
}
.
Furthermore, we define
V�(s)∶={s}
,
V�(z)∶={z}
, and
V�(v)∶={vt∈V�∣t∈[
𝓁
]}
,
for all
v∈V⧵{s,z}
.
Next, we show that a
𝛥
-(s,z)-expansion of a temporal graph can be computed
efficiently.
3 The algorithm always outputs no if there is no
𝛥
-restless temporal (s,z)-path and outputs otherwise yes
with constant probability.
2772 Algorithmica (2021) 83:2754–2802
1 3
Lemma 2 Given a temporal graph
G=(V,(Ei)i∈[
𝓁
])
, two distinct vertices
s,z∈V
,
and
𝛥≤𝓁
, we can compute its
𝛥
-(s,z)-expansion D with
|V(D)|∈O(|G|)
in
O(|G|⋅𝛥)
time.
Proof Let
V�∶= {s,z}
and
E′
be empty in the beginning. We will fill up
V′
and
E′
simultaneously. In order to do that efficiently, we will maintain for each ver-
tex
v∈V
a ordered list
Lv
such that
t∈Lv
if and only if
vt∈V�
. We assume that
�
V
�≤∑𝓁
i=1�
E
i�
, because vertices which are isolated in every layer are irrelevant for
the
𝛥
-(s,z)-expansion and can be erased in linear time.
We proceed as follows. For each
t∈{1, …,𝓁}
(in ascending order), we iterate
over
Et
. For each
{v,w}∈Et
, we distinguish three cases.
(
w=s
): We add
vt
to
V′
,
(s,vt)
to
E′
, and add t to
Lv
. This can be done
in constant time.
(
w=z
): We add
vt
to
V′
, and add t to
Lv
. Now we iterate over all
i∈Lv
(in descending order) and add
(vi
,z)
to
E′
until
t−i>𝛥
. This
can be done in
O(𝛥)
time.
(
{s,z}∩{v,w}=�
): We add
vt
,wt
to
V′
, and add t to
Lv
and
Lw
. Now we iterate
over
i∈Lv
(in descending order) and add
(vi
,wt)
to
E′
until
t−i>𝛥
. Afterwards, we iterate over
i∈Lw
(in descending
order) and add
(wi
,vt)
to
E′
until
t−i>𝛥
. This can be done
in
O(𝛥)
time.
Observe that after this procedure the digraph
D=(V�
,E�)
is the
𝛥
-(s,z)-expan-
sion of
G
and that we added at most 2 vertices for each time-edge in
G
. Hence,
V′≤|G|
. This gives a overall running time of
O(|G|⋅𝛥)
.
◻
It is easy to see that there is a
𝛥
-restless temporal
(s,z)
-walk in the temporal
graph if and only if there is an
(s,z)
-dipath in the
𝛥
-(s,z)-expansion. Next, we
identify the necessary side constraint to identify
𝛥
-restless temporal
(s,z)
-paths in
the
𝛥
-(s,z)-expansion.
Lemma 3 Let
G=(V,(Ei)i∈[
𝓁
])
be a temporal graph,
s,z∈V
two distinct vertices,
𝛥≤𝓁
, and
D=(V�
,E�)
the
𝛥
-(s,z)-expansion of
G
. There is a
𝛥
-restless temporal
(s,z)
-path in
G
of lengthk if and only if there is an
(s,z)
-dipath
P′
in D of length k
such that for all
v∈V
it holds that
|V�(v)∩V(P�)|≤1
.
Proof
(⇒)
: Let
P
=
(
((s,v
1
,t
1
),(v
1
,v
2
,t
2
),…,(v
k
�
−1
,z,t
k
�)
)
be a
𝛥
-restless temporal
(s,z)
-path in
G
of length k. We can inductively construct an
(s,z)
-dipath
P′
in D.
Observe that
P
�
1
∶= ((s,v
t
1
1))
is an
(
s,v
t
1
1)
-dipath of length 1 in D, because the arc
2773
1 3
Algorithmica (2021) 83:2754–2802
(
s,v
t
1
1)
is in
Es
of D. Now let
i∈[k�−2]
and
P′
i
be an
(
s,v
t
i
i)
-dipath of length i such
that
(i) for all
j∈[i]
, we have that
|V�(vj)∩V(P�
i)|=1
, and
(ii) for all
v∈V⧵{s,v1,…,vi}
, we have that
|V�(v)∩V(P�
i)|=0
.
In order to get an
(
s,v
t
i+1
i+1)
-dipath
P�
i+1
of length
i+1
, we extend
P′
i
by the arc
(
v
t
i
i
,v
t
i+1
i+1)
. Observe, that
vt
i+1
i+1
∈V
�
because of the time-edge
({vi,vi+1},ti+1)
in
G
and
that the arc
(
v
t
i
i
,v
t
i+1
i+1
)∈E
�
, because we have
0≤ti+1−ti≤𝛥
. Observe that
(i) for all
j∈[i+1]
, we have that
|V�(vj)∩V(P�
i+1)|=1
, and
(ii) for all
v∈V⧵{s,v1,…,vi+1}
, we have that
|V�(v)∩V(P�
i+1)|=0
.
Hence, we have an
(
s,v
t
k�−1
k�−1)
-dipath
P�
k−1
of length
k−1
satisfying (i) and (ii) which
can be extended (in a similar way) to an
(s,z)
-dipath of length k such that for all
v∈V
it holds that
|V�(v)∩V(P�)|≤1
.
(⇐)
: Let
P′
be a
(s,z)
-dipath in D of length k such that for all
v∈V
it holds that
|V�(v)∩V(P�)|≤1
. Let
V
(P�)={s,v
t
1
1
,…,v
t
k−1
k−1
,z
}
. Observe that an arc from s to
vt1
1
in D implies that there is a time-edge
({s,v1},t1)
in
G
. Similarly, an arc from
vti
i
to
vt
i+
1
i+1
implies that there is a time-edge
({vi,vi+1},ti+1)
in
G
and that
0≤ti+1−ti≤𝛥
,
for all
i∈[k−2]
. Moreover, an arc from
vt
k−1
k−1
to z implies that there is some
tk
such that there is a time-edge
({vk,z},tk)
in
G
with
0≤tk−tk−1≤𝛥
. Hence,
P
=
(
(s,v
1
,t
1
),(v
1
,v
2
,t
2
),…,(v
k
�
−1
,z,t
k
�)
)
is a
𝛥
-restless temporal
(s,z)
-walk of
length k in
G
. Finally,
|V�(v)∩V(P�)|≤1
, for all
v∈V
, implies that
vi≠vj
for all
i,j∈{0, …,k}
with
i≠j
. Thus, P is a
𝛥
-restless temporal
(s,z)
-path of length k.
◻
Obtaining Theorem3 (i) We now adapt the algorithm of Williams [60] to our spe-
cific needs. To this end, we introduce some standard notation from algebraic theory.
An arithmetic circuit C over a commutative ring R is a simple labelled directed
acyclic graph with its internal nodes labeled by
+
(sum gates) or
×
(product gates)
and its nodes of in-degree zero (input gates) labeled with elements from
R∪X
,
where X is a set of variables. There is one node of out-degree zero, called the output
gate. The size of C is the number of vertices in the graph. An arithmetic circuit C
over R computes a polynomial P(X) over R in the natural way: an input gate repre-
sents the polynomial it is labeled by. A sum (product) gate represents the sum (prod-
uct) of the polynomials represented by its in-degree neighbors. We say C represents
P(X) if the polynomial of the output gate of C is equivalent to P(X).
Lemma 4 Let
k∈ℕ
and
D=(V,A)
be a directed graph with partition
V
=
⨄n
i=0
V
i
,
where
V0={s}
and
Vn={z}
. Then, there is an arithmetic circuit C representing a
polynomial Q(X) of degree at most
k+1
such that Q(X) has a multilinear4 monomial
4 No variable occurs to a power of two or higher.
2774 Algorithmica (2021) 83:2754–2802
1 3
of degree at most
k+1
if and only if there is an
(s,z)
-path P of length at most k in D
where
|V(P)∩Vi|≤1
for all
i∈[n]
. Moreover,
|X|=n+1
, C is of size
O(k(n+|A|))
,
has no scalar multiplication, and all product gates in have in-degree two.
The idea of the polynomial is similar to the one of Williams [60], but here instead
of having one variable for each vertex we just have one variable for all vertices in
one part of the partition of V.
Proof We define the polynomial recursively as
Q
(X)=x
⊥
Q
k
z
over variables
X={x⊥,x0}∪{xi∣i∈[n]}
, where
Note that we can, by simply following (1), construct an arithmetic circuit C which
represents Q(X) in
O(k(n+|A|))
time such that each product gate has an in-degree of
two. Furthermore, observe that Q(X) has no scalar multiplication and is of degree at
most
k+1
.
The following induction completes the proof: We claim that for all
v∈V
and
j∈[k]∪{0}
, Q(X) has a multilinear monomial M of degree at most
j+1
if and
only if there is an
(s,v)
-path P of length at most j in D where
|V(P)∩Vi|≤1
for all
i∈[n]
. Moreover, M contains the variable
xi
if and only if
|V(P)∩Vi|=1
, for all
i∈[n]
. Is is easy to verify that the claim is true for
j=0
.
Now assume as induction hypothesis that for all
u∈V
and all
j�<j∈[k]
, the
polynomial
x⊥Qj′
u
has a multilinear monomial M of degree at most
j�+1
if and only
if there is an
(s,u)
-path P of length at most
j′
in D where
|V(P)∩Vi|≤1
, for all
i∈[n]
. Moreover, M contains the variable
xi
if and only if
|V(P)∩Vi|=1
, for all
i∈[n]
. Let
v∈Vp
.
(⇒)
: Assume there is a multilinear monomial M of degree at most
j+1
in
x⊥Qj
v
. Since
x⊥
Q
j
v=
∑(u,v)∈A
x
p
(x
⊥
Q
j−1
u
)
, we know that M contains
xp
and there is
a
(u,v)∈A
such that
x⊥Qj−1
u
contains a multilinear monomial
M′
which does not
contain
xp
. By induction hypothesis, there is an
(s,u)
-path
P′
of length at most
j−1
such that
|V(P�)∩Vi|=1
if and only if
M′
contains
xi
for all
i∈[n]
. Hence, there
is an
(s,v)
-path P (obtained by extending
P′
with v) such that
|V(P)∩Vi|≤1
for all
i∈[n]
. Furthermore, we have that
|V(P)∩Vi|=1
if and only if M contains
xi
for all
i∈[n]
.
(⇐)
: Assume there is an
(s,v)
-path P of length at most j in D where
|V(P)∩Vi|≤1
for all
i∈[n]
. Let
P′
be the
(s,u)
-path obtained by removing v from P. Hence,
P′
is
(1)
Q
0
s∶= x0,
∀v∈V⧵{s}∶Q0
v∶= x⊥
, and
∀
v∈V,∀j∈[k]∶Qj
v∶=
∑
(u,v)∈A
Qj−1
uxi, where v∈Vi
.
2775
1 3
Algorithmica (2021) 83:2754–2802
of length at most
j−1
, and
|V(P)∩Vi|≤1
for all
i∈[n]
. By induction hypothesis
x⊥
Q
j−1
u
contains a multilinear monomial M of degree at most j which does not con-
tain
xp
. Since
x⊥
Q
j
v
=
∑(u,v)∈A
x
p
(x
⊥
Q
j−1
u)
, we know that x
⊥
Q
j
v
contains a M multi-
plied by
xp
as monomial. Thus,
x⊥
Q
j
v
has a multilinear monomial of degree at most
j+1
which contains variable
xi
if and only if
|
V(P
�
)∩V
i|
=
1
, for all
i∈[n]
.
◻
Now we can apply the following result of Williams [60].
Theorem4 [60] Let Q(X) be a polynomial of degree at most k, represented by an
arithmetic circuit of size n with no scalar multiplications and where all product
gates have in-degree two. There is a randomized algorithm that runs in
2knO(1)
time,
outputs yes with high probability (
≥1
∕5
) if there is a multilinear term in the sum-
product expansion of Q, and always outputs no if there is no multilinear term.
Theorem3 (i) follows from Lemmas2 to 4 and Theorem4. This can be derandomized
by Theorem5.2 of Fomin etal.[32] resulting in
O(3.841k
⋅
(|
G
|𝛥)2|V|log |V|)
time
algorithm. We now show how to improve the polynomial part of a deterministic
algorithm.
Obtaining Theorem3 (ii) To show Theorem3 (ii), we first note that in the (s,z)-
expansion of an (s,z)-path P in the directed graph describes a
𝛥
-restless temporal
(s,z)
-path exactly when V(P) is an independent set of some specific matroid. We then
show an algorithm to find such a path P (if there is one). To this end, we introduce
a problem,
inDepenDent path
, and some standard terminology from matroid the-
ory[55]. A pair
(U,I)
, where Uis the ground set and
I⊆2U
is a family of independ-
ent sets, is a matroid if the following holds:
�∈I
; if
A′⊆A
and
A∈I
, then
A�∈I
;
and if
A,B∈I
and
|A|<|B|
, then there is an
x∈B⧵A
such that
A∪{x}∈I
. An
inclusion-wise maximal independent set
A∈I
of a matroid
M=(U,I)
is a basis.
The cardinality of the bases ofM is called the rank ofM. The uniform matroid of
rankr on U is the matroid
(U,I)
with
I={S⊆U∣|S|≤r}
. A matroid
(U,I)
is
linear or representable over a field
𝔽
if there is a matrixA with entries in
𝔽
and the
columns labeled by the elements ofU such that
S∈I
if and only if the columns
ofA with labels inS are linearly independent over
𝔽
. Such a matrix A is called a
representation of
(U,I)
. Now we are ready to state the
inDepenDent path
problem.
2776 Algorithmica (2021) 83:2754–2802
1 3
For the remainder of this section, whenever we speak about independent sets,
these are independent sets of a matroid and not a set of vertices which induce an
edgeless graph.
Agrawaletal.[1] studied, independently from us, a similar problem where the
edges of the path shall be an independent set of a matroid. To show Theorem3 (ii),
we need a single-exponential algorithm which has only a linear dependency on the
input size. To this end, we show the following, based on representative families.
Theorem5 An instance
(D,s,z,AM)
of
Independent path
can be solved in time of
O(2𝜔rm)
operations over the field
𝔽
, where
𝔽
is the field of
AM
, r is rank of M, m is
the number of edges in D, and
2<𝜔<2.373
is an upper-bound for the matrix mul-
tiplication exponent.5
In this section, we provide a fixed-parameter algorithm for
inDepenDent path
parameterized by rank r of the matroid. Since the rank r is at most |V(D)|, this algo-
rithm is asymptotically optimal, see Corollary3. To show Theorem5, we provide
an algorithm (Algorithm4.1), show its correctness (Lemma5), and prove the run-
ning time upper-bound (Lemma6). The idea of our algorithm is based on the algo-
rithm of Fominetal.[31] for k
-path
and independently from us Agrawaletal.[1]
showed an algorithm which runs in
2O(r)nO(1)
time for
inDepenDent path
and Lok-
shtanovetal.[48] provided a dynamic program, running in
5.18rnO(1)
time, for the
special case of
inDepenDent path
when the matroid given in the input is a transver-
sal matroid. However, in contrast to Agrawaletal.[1] and Lokshtanovetal.[48], we
pay attention to the detail that the algorithm behind Theorem5 runs in linear time, if
we can perform one field operation in constant time.
5 Note that we require
2<𝜔
even though this might be not true. We do this to upper-bound the polyno-
mial part in r. The bound
𝜔<2.373
is known [6].
2777
1 3
Algorithmica (2021) 83:2754–2802
The main tool of our algorithm are representative families of independent sets.
Definition 3 (Representative family) Given a matroid
(U,I)
, and afamily
S⊆2U
,
we say that a subfamily
�
S⊆S
is a q-representative for
S
if, for each set
Y⊆U
of
size at mostq, it holds that:
– if there is a set
X∈S
with
X⊎Y∈I
,
– then there is a set
X∈
S
with
�
X⊎Y∈I
.
A p-family is a family
F
such that each set
S∈F
is of size exactly p. For lin-
ear matroids, we can compute small representative families efficiently. Formally,
the following is known.
Theorem6 (Fomin etal.[31, Theorem1.1]) Let
M=(U,I)
be a linear matroid of
rank
r=p+q
given together with its representation
AM
over field
𝔽
. Let
S
be a
p-family of independents of M. Then a q-representative family
�
S⊆S
of size at most
(r
p)
can be found in
O((
r
p)
tp𝜔+t
(
r
q)𝜔
−1
)
operations over
𝔽
, where
𝜔<2.373
is the
matrix multiplication exponent.
We are now ready to give the pseudo-code of the algorithm behind Theorem5
(see Algorithm4.1).
In Algorithm 4.1,
A∙MB
is defined as
{A∪B∣A∈A,B∈B,A∩B=�,A∪B∈I}
for families
A,B⊆I
and matroid
M=(U,I)
.
Lemma 5 Algorithm4.1 is correct.
Proof Let
Pw,i∶= {
X
∈I∣
there is an
(s,w)
-dipath P of length i such that
V(P)=X}
,
for all
w∈V
and
i∈[r−1]
. Observe that
Pw,i
is an
(i+1)
-family of independent
sets. We show by induction that after iteration i of the for-loop in Line (3) the entry
T[w,i] is an
(r−i)
-representative of
Pw,i
, for all
w∈V
and
i∈[r−1]
. Then the cor-
rectness follows, since we check after each of these iterations whether T[w,i] is non-
empty (Line (9)). Observe that
Ps,0 ={s}
and
Pv,0 =�
for all
v∈V⧵{s}
. Hence,
the entries of T computed in Lines (1) and (2) fulfill our induction hypothesis.
Now let
i∈[r−1]
be the current iteration of the for-loop in Line (3) and assume
that for all
j<i
we have that T[w,j] is an
(r−j)
-representative of
Pw,j
, for all
w∈V
.
Fix a vertex
w∈V
. We first show that if there is an
X∈T[i,w]
, then there is an
(s,w)
-dipath
Pw
of length i such that
X=V(Pw)∈I
. Observe that in Lines (5)–(7)
we look at each possible predecessor
v∈V
of w in an
(s,w)
-dipath of length i, take
each set
X�∈T[v,i−1]
and check whether
X�∪{w}
is an independent set of size
i+1
. If this is the case, we add it to
Nw,i
. After Line (8), we have that
T[
w,i
]⊆Nw,i
.
Since
X�∈T[v,i−1]
, we know that there is an
(s,v)
-dipath
Pv
of length
i−1
with
X�=V(P)
. Thus, if there is an
X∈T[i,w]
, then there is an
(s,w)
-dipath
Pw
of length
i such that
X=V(Pw)∈I
2778 Algorithmica (2021) 83:2754–2802
1 3
Now let
X∈Pw,i
and
Y⊆V(D)
be a set of vertices of size at most
r−i−1
such that
X∩Y=�
and
X⊎Y∈I
. Hence, there is an
(s,w)
-dipath P of length
i such that
V(P)=X
. Let v be the predecessor of w in P. Let
Pv
be the
(s,v)
-dipath of length
i−1
induced by P without w. Hence,
V(Pv)∈Pv,i−1
. Moreover,
V(Pv)∩(Y∪{v}) = �
and
V(Pv)⊎(Y∪{w}) ∈ I
. Since
T[v,i−1]
is an
(r−i+1)
-representative family of
Pv,i−1
, we know that there is an
X∈T[v,i−1]
such that
X∩(Y∪{w}) = �
and
X∪(Y∪{w}) ∈
I . In Lines (5)–(7) we add
X∪{w}
to
Nw,i
.
Let
X
�
∶=
X∪{w}
and note that
X�∩Y=�
and
X�⊎Y∈I
. Since T[w, i] is an
(r−i)
-representative family of
Nw,i
, we know that there is an
X
�
∈T[w,i]
such that
X
�
∩Y=�
and
X�⊎Y∈I
. Thus, T[w,i] is an
(r−i)
-representative of
Pw,i
.
◻
Next, we show that Algorithm4.1 is actually a fixed-parameter algorithm param-
eterized by the length of a shortest
𝛥
-restless temporal (s,z)-path.
Lemma 6 Algorithm4.1 runs in time of
O(2𝜔r
⋅m)
operations over
𝔽
, where
𝔽
is the
field of
AM
, r is the rank of the matroid, m is the number of edges, and
2<𝜔<2.373
is an upper-bound for the matrix multiplication exponent.
Proof Without loss of generality we assume to have a total ordering on V. We repre-
sent a subset of V as a sorted string. Hence, union and intersection of two sets of size
at most r takes O(r) time. We can thus look up and store sets of size at most r in a
trie (or radix tree) in O(r) time [21]. Note that we do not have the time to completely
initialize the arrays of size |V| in each trie node. Instead, we will initialize each array
cell of a trie node at its first access. To keep track of the already initialized cells, we
use sparse sets over V which allows membership test, insertion, and deletion of ele-
ments in constant time [16].
We denote the in-neighborhood of a vertex w by
N−(w)∶={v∈V∣(v,w)∈E}
.
Furthermore, let
Hi,w
be the running time of Lines (5)–(7) in iteration i of the for-
loop in Line (3), and
Ri,w
be the number of operations over
𝔽
of Line (8) in iteration i
of the for-loop in Line (3). Then we can run Algorithm 4.1 in time of
O�∑
r−1
i=1
∑
w∈VHi,w+
∑
r−1
i=1
∑
w∈VRi,w
�
operations over
𝔽
—that is, the running time
respecting the time needed for operations over
𝔽
. Let
i∈[r−1]
and
w∈V
. In the i-
th iteration of the for-loop in Line (3),
|
T[v,j]
|≤(r
j+1)
for all
j<i
and
v∈V
, since
we used Theorem6 in prior iterations. Let
2<𝜔<2.373
be an upper-bound for the
matrix multiplication exponent. Hence,
|N
w,i
|≤(r
i+1)|
N
−
(w)
|
and
H
i,w∈O(
(r
i+1)|
N
−
(w)
|
⋅r
𝜔)
, because the independence test can be done via matrix
multiplication. Thus,
2779
1 3
Algorithmica (2021) 83:2754–2802
Moreover, by Theorem6, we have
where the last inclusion is true because we assume
2<𝜔
.
Thus, we can run Algorithm4.1 in time of
O(2𝜔rm)
operations over
𝔽
.
◻
Now Theorem5 follows from Lemmas6 and 5.
Observe that by Lemma3, there is a
𝛥
-restless temporal
(s,z)
-path in the tem-
poral graph
G
if and only if there is an (s, z)-path P in the
𝛥
-(s, z)-expansion
D=(V�
,E�)
of
G
such that V(P) is an independent set in the partition matroid6
M=(V�,{X⊆V�∣∀v∈V∶|X∩V�(v)|≤1})
. Note that M is of rank |V| and hence
too large to show Theorem3 with Theorem5.
A k-truncation of a matroid
(U,I)
is a matroid
(U,{X∈I∣|X|≤k})
such that
all independent sets are of size at most k. The k-truncation of a linear matroid
is also a linear matroid [49]. In our reduction from
shoRt Restless tempoRal
path
to
inDepenDent path
we use a
(k+1)
-truncation of matroid M. Two general
approaches are known to compute a representation for a k-truncation of a linear
matroid—one is randomized [49] and one is deterministic [47].7 Both approaches
require a large field implying that one operation over that field is rather slow.
However, for our specific matroid we employ the Vandermonde matrix to compute
a representation over a small finite field. Note that we would not get a running
time linear in the input size by applying the algorithm of Lokshtanovetal.[47] or
Marx[49] on M.
Lemma 7 Given a universe U of size n, a partition
P1⊎⋯⊎Pq=U
, and an integer
k∈ℕ
, we can compute in O(kn) time a representation
AM
for the matroid
M
=
(
U,
{
X⊆U
||||
X
|
≤kand ∀i∈[q]∶
|
X∩Pi
|
≤1
})
, where
AM
is defined
over a finite field
𝔽
and one operation over
𝔽
takes constant time.
Proof For this running time analysis we assume the Word RAM model of computa-
tion, introduced by [34], which is similar to the RAM model of computation but one
O(r−1
∑
i=1
∑
w∈V
Hi,w
)
⊆O
(r−1
∑
i=1
∑
w∈V
|
N−(w)
|(
r
i+1
)
⋅r𝜔
)
⊆O
(
2r+o(r)m
).
O(r−1
∑
i=1∑
w∈V
Ri,w
)
⊆O
(r−1
∑
i=1
m
(
r
i
)(
r
i+1
)
(i+1)𝜔+
r−1
∑
i=1
m
(
r
i
)(
r
r−i−1
)𝜔−
1
)
⊆O
(
2rm(2rr𝜔+2r(𝜔−1))
)
⊆O
(
m(22r+log2(r)𝜔+2r𝜔)
)
⊆O(2𝜔rm)
,
6 Partition matroids are linear [49].
7 For both algorithms, a representation of the original matroid must be given.
2780 Algorithmica (2021) 83:2754–2802
1 3
memory cell can store only
O(log n)
many bits, where n is the input size. This avoids
abuse of the unit cost random access machine by for example multiplying very large
numbers in constant time.
Without loss of generality we assume that
q≤n
. Let p be a prime number with
q≤p≤2q
. Such a prime exists by the folklore Betrand-Chebyshev Theorem [2]
and can be computed in O(n) time using Lagarias-Odlyzko Method[58]. To perform
one operation on the prime field
𝔽p
, one can first perform the primitive operation in
ℤ
and them take the result modulop. Since
p≤2q∈O(n)
, each element of
𝔽p
fits
into one cell of the Word RAM model of computation. Thus, we can perform one
operation over
𝔽p
in constant time.
Let
x1,…,xq
be pair-wise distinct elements from
𝔽p
. To compute an
(k×n)
-matrix
AM
as representation for M over
𝔽p
, we compose (column-wise) for each ele-
ment
u∈Pi
the vector
𝐯i
∶=
(
x0
i
x1
i
…xk−1
i)T
, where
i∈[q]
. That gives a running
time of
O(k⋅n)
operations over
𝔽p
, since we can compute
𝐯i
in O(k) operations over
𝔽p
.
It remains to show that
AM
is a representation of M. Let
X⊆U
. If there is an
i∈[p]
such that
|X∩Pi|>1
, then the corresponding columns of
AM
are linearly
dependent, because we have the vector
𝐯i
twice. Now we assume that for all
i∈[q]
we have
|X∩Pi|≤1
. Furthermore, if
|X|>k
, then we know that the correspond-
ing columns of
AM
are linearly dependent, because
AM
is an
(k×n)
-matrix. We can
observe that if
|X|=k
, then the corresponding columns in
AM
form a Vandermonde
matrix, whose determinate is known to be non-zero. Hence, if
|X|≤k
, then the cor-
responding columns in
AM
are linearly independent. Thus,
AM
is a representation
ofM.
◻
We now show a reduction from
shoRt Restless tempoRal path
to
inDepenDent
path
using Lemmas2, 3 and 7
Lemma 8 Given an instance
(G,s,z,k,𝛥)
of
shoRt Restless tempoRal path
, we
can compute in
O(max{k,𝛥}⋅|G|)
time an instance
(D,s,z,AM)
of
Independent
path
such that M has rank
k+1
, and
(G,s,z,k,𝛥)
is a yes-instance if and only if
(D,s,z,AM)
is a yes-instance, where one operation over the finite field of
AM
takes
constant time.
Proof Let
(G=(
V,
(
E
i)i∈[
𝓁
])
,s,z,k,
𝛥)
be an instance of
shoRt Restless tempoRal
path
. We construct an instance
(D,s,z,AM,k)
of
inDepenDent path
in the following
way. Let digraph
D=(V�
,E�)
be the
𝛥
-(s,z)-expansion of
G
which can be computed,
by Lemma2, in
O(|G|
⋅
𝛥)
time such that
V�∈O(|G|)
. Observe that
⋃v∈V
V
�(
v
)
is a
partition of
V′
. Now, we construct a representation
AM
(over a finite field where we
can perform one operation in constant time) of the matroid
2781
1 3
Algorithmica (2021) 83:2754–2802
in
O(k⋅|G|)
time by Lemma7. Note that M is an
(k+1)
-truncated partition matroid
and hence has rank
k+1
. This completes the construction and gives us an overall
running time of
O(max{k,𝛥}⋅|G|)
.
We now claim
(G,s,z,k,𝛥)
is a yes-instance if and only if
(D,s,z,AM)
is a yes-
instance and contains an independent
(s,z)
-dipath of length at most k.
(⇐)
: Let P be a
𝛥
-restless temporal
(s,z)
-path of length
k′≤k
in
G
. Then, by
Lemma 3 there is an
(s,z)
-dipath
P′
of length
k′
such that for all
v∈V
it holds
that
|V�(v)∩V(P�)|≤1
. Since
|V(P�)|=k�+1≤k+1
, we know that
V(P�)
is an
independent set of M. Thus,
P′
is a witness of length at most k for
(D,s,z,AM)
being
a yes-instance.
(⇒)
: Let
P′
be an
(s,z)
-dipath of length
k′≤k
in D such that
V(P�)
is an independ-
ent set of M. Clearly, for
v∈V
it holds that
|V�(v)∩V(P�)|≤1
. Then, by Lemma3,
there is a
𝛥
-restless temporal
(s,z)
-path of length
k′
in
G
.
◻
Proof of Theorem3 (ii) Let
I=(G=(V,(Ei)i∈[
𝓁
]),s,z,k,𝛥)
be an instance of
shoRt
Restless tempoRal path
.
To decide whether there is a witness of length k of I being a yes-instance, we
first use Lemma8 to compute an instance
I�=(D,s,z,AM)
of
inDepenDent path
in
O(|G|⋅max{𝛥,k})
time, where we can compute one operation over the field
𝔽
of
AM
in constant time and the matroid M which is represented by
AM
is of rank
k+1
. Note
that
I′
is a yes-instance if and only if there is witness of length k for I being a yes-
instance. Second, we solve
I′
by Theorem5 in
O(2𝜔(k+1)
⋅
|G|
⋅
𝛥)
time.
Thus, we have an overall running time of
2O(k)
⋅
|G|
⋅
𝛥
.
◻
Moreover, from Lemma8 it is intermediately clear that the lower-bounds of
Corollary1 and Theorem1 translate to
inDepenDent path
.
Corollary 3
Independent path
is NP-hard and unless the ETH fails there is no
2o(n)
-time algorithm for it, where n is the number of vertices.
Note that from Theorem1 we can further deduce that there is not much hope for
fast or early restless temporal paths, that is, restless temporal path that have a small
duration or an early arrival time. The instance constructed in the reduction has life-
time
𝓁=3
and hence the duration as well as the arrival time of any restless temporal
path in this instance is at most three. This implies that we presumably cannot find
fast or early restless temporal paths efficiently.
M
=
(
V�,
{
X⊆V�
|||
X
|
≤k+1 and ∀v∈V∶
|
X∩V�(v)
|
≤1
})
2782 Algorithmica (2021) 83:2754–2802
1 3
5 Computational Complexity Landscape fortheUnderlying Graph
In this section we investigate the parameterized computational complexity of
Rest
-
less tempoRal path
when parameterized by structural parameters of the underly-
ing graph. We start by observing that whenever a parametrization forbids path of
unbounded length, then we can use Theorem3 to show fixed-parameter tractability.
For example, if we consider the vertex cover number
vc↓
of the underlying graph,
then we can deduce that any path in the underlying graph and hence any restless
temporal path can have length at most
2vc↓+1
. Thus, by Theorem3, we get fixed-
parameter tractability of
Restless tempoRal path
when parameterized by the vertex
cover number of the underlying graph.
Observation 3
Restless tempoRal path
parameterized by the vertex cover number
vc↓
of the underlying graph is fixed-parameter tractable.
From a classification standpoint, we can improve this a little further by observ-
ing that the length of a path in the underlying graph can be bounded by
2O(td
↓
)
[53],
where
td↓
is the treedepth of the underlying graph.
Observation 4
Restless tempoRal path
parameterized by the treedepth
td↓
of the
underlying graph is fixed-parameter tractable.
One of the few dark spots of the landscape is the feedback edge number8 of the
underlying graph which is resolved in the following way.
Theorem7
Restless tempoRal path
can be solved in
2
O(−
∫
)⋅
|
G
|
time, where
−
∫
is the
feedback edge number of the underlying graph.
By Corollary1 we know that Theorem7 is asymptotically optimal, unless ETH
fails. In a nutshell, our algorithm to prove Theorem7 has the following five steps:
1. Exhaustively remove all degree-1 vertices from
G↓
(except for s and z).
2. Compute a minimum-cardinality feedback edge setF of the graph
G↓
.
3. Compute a set
P
of
O
(−
∫)
many paths in
G↓
−F
such that every path in
G↓
−F
is
a concatenation of some paths in
P
.
4. “Guess” the feedback edges in F and paths in
P
of an (s,z)-path in
G↓
.
5. Verify whether the “guessed” (s,z)-path is a
𝛥
-restless temporal
(s,z)
-path in
G
.
First, we show that we can safely remove all (except s and z) degree-one vertices
from the underlying graphs
G↓
.
8 For a given graph
G=(V,E)
a set
F⊆E
is a feedback edge set if
G−F
does not contain a cycle. The
feedback edge number of a graph G is the size of a minimum feedback edge set for G.
2783
1 3
Algorithmica (2021) 83:2754–2802
Reduction Rule 1 (Low Degree Rule) Let
I=(G=(V,(Ei)i∈[
𝓁
]),s,z,𝛥)
be an
instance of
Restless tempoRal path
,
G↓
be the underlying graph of
G
,
v∈V⧵{s,z}
,
and
deg
G
↓(v)≤1
. Then, output
(G−{v},s,z,𝛥)
.
Lemma 9 ReductionRule1 is safe and can be applied exhaustively in
O(|G|)
time.
Proof Let
I=(G=(V,(Ei)i∈[
𝓁
]),s,z,𝛥)
be an instance of
Restless tempoRal path
,
For the safeness we can observe that a vertex
v∈V⧵{s,z}
with
deg
G
↓(v)≤1
cannot
be visited by any
𝛥
-restless temporal
(s,z)
-path. To apply ReductionRule1 exhaus-
tively, we iterate once over the set of time edges to store for each vertex
v∈V⧵{s,z}
its degree in a counter
cv
. Afterwards, we collect all vertices of degree 0 in X and all
vertices of degree 1 in
V1
. Now we iterate over each vertex
v∈V1
, remove v from
V1
,
add v to X, decrement the counter
cu
of its neighbor u. If
cu
becomes1 we add u to
V1
. Note that this procedure ends after O(|V|) time.
Finally, we iterate one last time over the temporal graph
G
to construct the tem-
poral graph
G�∶= G−X
. The instance
(G�
,s,z,𝛥)
of
Restless tempoRal path
is the
resulting instance when we apply ReductionRule1 exhaustively on I.
◻
Next, we consider a static graphG with no degree-one or degree-zero vertices.
Let F be an minimum feedback edge set of G and let
VF
be the endpoints of the
edges inF, that is
VF={v∈e∣e∈F}
. Let
V≥3
be the set of all vertices with a
degree greater than two in
G−F
. We can partition the graph
G−F
into a set
P
of
VF
∪V
≥3
-connecting paths, that are, all paths in
G−F
who start and end in
VF
∪V
≥3
and have no internal vertices in that set of vertices. Note that all degree-one vertices
of
G−F
are in
VF
. Hence, the graph
G−F
can be partitioned into
VF
∪V
≥3
-con-
necting paths. We can show that
|P|
∈O(−
∫)
.
Lemma 10 Let G be a graph with no degree-one vertices and F be an minimum feed-
back edge set of G. The set
P
of
VF∪V≥3
-connecting paths of
G−F
has sizeO(|F|)
and can be computed inO(|G|) time.
Proof We can compute the set
P
in O(|G|) time as follows. We start with
P=�
and pick any leaf
v∈V(G−F)
of degree one. Recall that
v∈VF
and that
G−F
is cycle-free. There is at most one vertex
w
∈(V
≥3
∪V
F
)
⧵
{v
}
such that there is
a path P between v and w which does not contain internal vertices from
V≥3
∪V
F
.
Note that also P is unique. We add P to
P
and remove
V(P)⧵{w}
from the graph.
Now we repeat this procedure with the next leaf of degree one until the graph has no
edges.
It is easy to verify that the number of paths is bounded by the number of verti-
ces in
V≥3
∪V
F
. We know that
|VF|
is upper-bounded by2|F|. It remains to show
that
|V≥3|
is in O(|F|).
2784 Algorithmica (2021) 83:2754–2802
1 3
As shown by Bentert etal. [9, Lemma 2], the number of vertices with degree
greater or equal to three is bounded by 3|F| in a graph with no degree-one vertices.
Hence, the number of
VF
∪V
≥3
-connecting paths is bounded by5|F|.
◻
With Lemmas9 and 10 we can prove Theorem7.
Proof of Theorem7 Let
I=(G=(V,(Ei)i∈[
𝓁
]),s,z,𝛥)
be an instance of
Restless
tempoRal path
and
G↓
be the underlying graph of
G
. Without loss of generality, we
can assume that all vertices in
V(G↓)⧵{s,z}
have a degree greater than one. If this is
initially not the case, then we safely remove all degree-one vertices of the underly-
ing graph exhaustively in
O(|G|)
time by Lemma9.
First we compute an minimum feedback edge set F of
G↓
in
O(|G↓|)
time. Then,
we compute the set
P
of
VF
∪V
≥3
∪{s,z
}
-connecting paths of
G↓
−F
in
O(|G↓|)
time by Lemma10. Note that the additional vertices s and z can increase the size of
P
by at most four. Now, for any subset of feedback edges
F′⊆F
and
P′⊆P
, we
check whether
F�∪E(P�)
form an (s,z)-pathP in
G↓
where
E
(
P�
) ∶=
⋃P
�
∈P
�E(P
�)
.
This can be decided in
O(|G↓|)
time by a simple breadth-first search on
G↓
start-
ing at the vertexs and using only edges in
F�∪E(P�)
. Last, we verify whether P
forms a
𝛥
-restless temporal
(s,z)
-path in
G
. Therefore, we consider the temporal
graph
GP=(V,(Ei∩E(P))i∈[
𝓁
])
which has P as underlying graph. Note that we can
construct
GP
in
O(|G|)
time, by iterating once over the set of time edges of
G
. By
Lemma1 we can decide in
O(|GP|)
time whether
GP
has a
𝛥
-restless temporal
(s,z)
-path.
It is easy to check that the algorithm described above runs in
2O(|F|)|G|
time.
Correctness. It remains to show the correctness of the algorithm.
(⇒)
: If our algorithm outputs yes, then there is a
𝛥
-restless temporal
(s,z)
-path
in
GP
. The temporal graph
GP
contains a subset of the time edges of
G
, hence
the
𝛥
-restless temporal
(s,z)
-path in
GP
is also present in
G
. It follows that I is a
yes-instance.
(⇐)
: Assume I is a yes-instance. Then there exists a
𝛥
-restless temporal
(s,z)
-
path in the temporal graph
G
. Let
P
=
(
(v
0
,v
1
,t
1
),…,(v
k−1
,v
k
,t
k
)
)
be such a path.
Hence,
P�
=
(
{v
0
,v
1
},…,{v
n−1
,v
n
}
)
is an (s,z)-path in the underlying graph
G↓
.
Let
F�=F∩E(P�)
. If we remove the edges in
F′
from
P′
then what remains is a col-
lection of paths where each path is a concatenation of paths in
P
. Hence, there exists
a subset
P′⊆P
such that
F�∪E(P�)=E(P)
. Thus, we will find
P′
in
G↓
and, by
Lemma1, we will correctly verify that this
P′
forms a
𝛥
-restless temporal
(s,z)
-path
in
G
.
◻
The results from Sects. 3 to 5 provide a good picture of the parameterized
complexity landscape for
Restless tempoRal path
, meaning that for most of the
2785
1 3
Algorithmica (2021) 83:2754–2802
widely known (static) graph parameters we know whether the problem is in FPT
or W[1]-hard or para-NP-hard, see Fig.2.
Our understanding of the class of temporal graphs where we can solve
Rest
-
less tempoRal path
efficiently narrows down to the following points. We can
check efficiently whether there is a
𝛥
-restless temporal
(s,z)
-path P in temporal
graph
G
if
1. there is a bounded number of (s,z)-path in
G↓
(cf.Theorem7 and Lemma1),
2. there is a bound on the length of P (cf.Theorem3 and Observations 4 and 3).
Apart from that we established with Theorems 1, 2 and Corollary 2 hardness
results for temporal graphs having restricted underlying graphs, see Fig.2.
Finally, we show that we presumably cannot expect to obtain polynomial ker-
nels for all parameters considered so far and most structural parameters of the
underlying graph.
Proposition 1
Restless tempoRal path
parameterized by the number n of vertices
does not admit a polynomial kernel for all
𝛥≥1
unless NP
⊆
coNP/poly.
We employ the OR-cross-composition framework byBodlaender, Jansen, and
Kratsch[15] to refute the existence of a polynomial kernel for a parameterized
problem under the assumption that NP
⊈
coNP/poly, the negation of which would
cause a collapse of the polynomial-time hierarchy to the third level. In order to
formally introduce the framework, we need some definitions.
An equivalence relationR on the instances of some problemL is a polynomial
equivalence relation if
1. one can decide for each two instances in time polynomial in their sizes whether
they belong to the same equivalence class, and
2. for each finite setS of instances, R partitions the set into at most
(maxx∈S|x|)O(1)
equivalence classes.
Using this, we can now define OR-cross-compositions.
Definition 4 An OR-cross-composition of a problem
L⊆Σ∗
into a parameterized
problem P (with respect to a polynomial equivalence relation R on the instances
of
L
) is an algorithm that takes n R-equivalent instances
x1,…,xn
ofL and con-
structs in time polynomial in
∑n
i=1�
x
i�
an instance (x,k) of
P
such that
1. k is polynomially upper-bounded in
max1≤i≤n|xi|+log(n)
and
2. (x,k) is a yes-instance of P if and only if there is an
i∈[n]
such that
xi
is a yes-
instance of L.
If an NP-hard problem
L
OR-cross-composes into a parameterized problem P,
thenP does not admit a polynomial kernel, unless NP
⊆
coNP/poly [15].
2786 Algorithmica (2021) 83:2754–2802
1 3
Proof of Proposition1 We provide an OR-cross-composition from
Restless tempo
-
Ral path
onto itself. We define an equivalence relationR as follows: Two instances
(G=(V,(Ei)i∈[
𝓁
]),s,z,𝛥)
and
(G�
=(V
�
,(E
�
i
)
i∈[
𝓁�
]
),s
�
,z
�
,
𝛥�)
are equivalent underR if
and only if
|V|=|V�|
and
𝛥=𝛥�
. Clearly, R is a polynomial equivalence relation.
Now let
(G1=(V1,(E1,i)i∈[
𝓁
1]),s1,z1,𝛥),…,(Gn=(Vn,(En,i)i∈[
𝓁
n]),sn,zn,𝛥)
be
R-equivalent instances of
Restless tempoRal path
. We construct a temporal graph
G⋆
=(V
⋆
,(E
⋆
i
)
i∈[
𝓁⋆
])
as follows. Let
|
V
⋆|
=
|
V
1|
and
s⋆
,z⋆∈V⋆
. We identify all
vertices
si
with
i∈[n]
with each other and with
s⋆
, that is,
s⋆
=s
1
=…=s
n
. Anal-
ogously, we identify all vertices
zi
with
i∈[n]
with each other and with
z⋆
, that is,
z⋆
=z
1
=…=z
n
. We arbitrarily identify the remaining vertices of the instances
with the remaining vertices from
V⋆
, that is, let
V⋆⧵
{s
⋆
,z
⋆
}=V
1⧵
{s
1
,z
1
}=…=V
n⧵
{s
n
,z
n}
. Now let
E⋆
1=E1,1,E
⋆
2=E1,2,…,E
⋆
𝓁
1
=E1,𝓁
1
. Intuitively, the first instance
(G1=(V1,(E1,i)i∈[
𝓁
1])
essentially forms the first
𝓁1
layers of
G⋆
. Then we introduce
𝛥+1
trivial layers, that is,
E⋆
𝓁
1+1
=E
⋆
𝓁
1+2
=…=E
⋆
𝓁
1+𝛥+1=�
. Then we continue in
the same fashion with the second instance and so on. We have that
𝓁⋆=∑i∈[n]𝓁i+(n−1)⋅(𝛥+1)
.
This instance can be constructed in polynomial time and the number of vertices
is the same as the vertices in the input instances, hence
|V⋆|
is polynomially upper-
bounded by the maximum size of an input instance. Furthermore, it is easy to check
that
G⋆
contains a
𝛥
-restless temporal
(s⋆
,z⋆)
-path if and only if there is an
i∈[n]
such that
Gi
contains a
𝛥
-restless temporal
(si,zi)
-path. This follows from the fact that
all instances are separated in time by
𝛥+1
trivial layers, hence no
𝛥
-restless tempo-
ral
(s⋆
,z⋆)
-path can use time edges from different original instances. Since
Restless
tempoRal path
is NP-hard (Theorem1) the result follows.
◻
6 Timed Feedback Vertex Number
In this section we introduce a new temporal version of the well-studied “feed-
back vertex number”-parameter. Recall that by Theorem2 we know that
Restless
tempoRal path
is W[1] -hard when parameterized by the feedback vertex num-
ber of the underlying graph. This motivates studying larger parameters with the
goal to obtain tractability results. We propose a new parameter called timed feed-
back vertex number which, intuitively, quantifies the number of vertex appear-
ances that need to be removed from a temporal graph such that its underlying
graph becomes cycle-free. Note that having vertex appearances in the deletion
set allows us to “guess” when we want to enter and leave the deletion set with a
𝛥
-restless temporal
(s,z)
-path in addition to guessing in which order the vertex
appearances are visited.
We remark that there also have been studies of removing (time) edges from
temporal graph to destroy temporal cycles[36], that is, temporal paths from a
2787
1 3
Algorithmica (2021) 83:2754–2802
vertex back to itself. Similarly, one also could remove vertex appearances to
destroy temporal cycles, resulting in a parameter that is smaller than the timed
feedback vertex number and incomparable to the feedback vertex number of the
underlying graph. Note that the mentioned parameters aiming at destroying tem-
poral cycles are unbounded in our reductions. We leave the parameterized com-
plexity of
Restless tempoRal path
with respect to those parameters open for
future research.
Before defining timed feedback vertex number formally, we introduce nota-
tion for removing vertex appearances from a temporal graph. Intuitively, when
we remove a vertex appearance from a temporal graph, we do not change
its vertex set, but remove all time edges that have the removed vertex appear-
ance as an endpoint. Let
G=(V,(Ei)i∈[
𝓁
])
be a temporal graph and
X⊆V×[𝓁]
a set of vertex appearances. Then we write
G
−X∶= (V,(E
�
i
)
i∈[
𝓁
])
, where
E�
i
=E
i⧵
{e∈E
i
∣ ∃(v,i)∈Xwith v∈e
}
. Formally, the timed feedback vertex
number is defined as follows.
Definition 5 (Timed Feedback Vertex Number) Let
G=(
V,
(
E
i)i∈[
𝓁
])
be a temporal
graph. A timed feedback vertex set of
G
is a set
X⊆V×[𝓁]
of vertex appearances
such that
G↓(G−
X
)
is cycle-free. The timed feedback vertex number of a temporal
graph
G
is the minimum cardinality of a timed feedback vertex set of
G
.
We can observe that for any temporal graph the timed feedback vertex number
is as least as large as the feedback vertex number of the underlying graph and
upper-bounded by the product of the feedback vertex number of the underlying
graph and the lifetime. We further remark that the timed feedback vertex number
is invariant under reordering the layers. At the end of this section we show how a
timed feedback vertex set can be computed efficiently.
The main result of this section is that
Restless tempoRal path
is fixed-param-
eter tractable when parameterized by the timed feedback vertex number of the
input temporal graph. To this end, we show the following.
Theorem 8 Given a timed feedback vertex set X of size
x
for a temporal
graph
G=(
V,
(
E
i)i∈[
𝓁
])
, we can decide in
O(6xx!
⋅
max{|G|3,|V|4x2})
time, whether
there is a
𝛥
-restless temporal (s,z)-path in
G
, where
s,z∈V
,
𝛥∈ℕ
.
The algorithm we present to show Theorem 8 solves
choRDal multicoloReD
inDepenDent set
, where given a chordal graph9
G=(V,E)
and a vertex coloring
c∶V→[k]
, we are asked to decide whether G contains an independent set of size
k that contains exactly one vertex of each color. This problem is known to be NP-
complete[13, Lemma2] and solvable in
O(3k
⋅
|V|2)
time[10, Proposition5.6]. Our
algorithm for
Restless tempoRal path
roughly follows these computation steps:
9 A graph is chordal if it does not contain induced cycles of length four or larger.
2788 Algorithmica (2021) 83:2754–2802
1 3
1. “Guess” which of and in which order the vertex appearances from the timed
feedback vertex set appear in the
𝛥
-restless temporal
(s,z)
-path.
2. Compute the path segments between two timed feedback vertex set vertices by
solving a
choRDal multicoloReD inDepenDent set
instance.
We give a precise description of our algorithm in Algorithm6.1. Here, a partition
O⊎I⊎U
of a set of vertex appearances X is valid if we have
v≠v′
, for all distinct
(v,t),(v�
,t�)∈I
and for all distinct
(v,t),(v�
,t�)∈O
. A vertex appearance
(v,t)∈I
signals that a
𝛥
-restless temporal
(s,z)
-path arrives in v at timet and
(v,t)∈O
sig-
nals that it departs from v at time t. Let
M∶= O∪I∪ ({s,z}×{⊥})
. We call a
linear ordering
(v0,t0)≤M⋯≤M(vx+1,tx+1)
of M a
𝛥
-ordering if
(v0,t0)=(s,⊥)
,
(vx+1,tx+1)=(t,⊥)
,
ti≤tj
if and only if
i<j∈[x]
, and for all
v∈V
with
(v,ti)∈I
and
(v,tj)∈O
it holds that
i+1=j
and
ti≤tj≤ti+𝛥
. Moreover, observe that for
a vertex appearance
(v,t)∈I
, the
𝛥
-restless temporal
(s,z)
-path has to depart from
v not later than
t+𝛥
and for vertex appearance
(v,t)∈O
, it has to arrive in v not
earlier than
t−𝛥
. To this end, we define the notion of a valid path between two con-
secutive vertex appearances:
Definition 6 Let
O⊎I⊎U
be a valid partition of X, and let
(vi,ti),(vi+1,ti+1)∈I∪O∪ ({s,z}×{⊥})
with
vi≠vi+1
, and P a
𝛥
-restless temporal
(vi,vi+1)
-path with departure time
td
and arrival time
ta
. Then P is
(ti,ti+1,I,O)
-valid
if the following holds true
2789
1 3
Algorithmica (2021) 83:2754–2802
(i)
(vi,ti)∈I
⟹
ti≤td≤ti+𝛥
,
(ii)
(vi,ti)∈O
⟹
td=ti
,
(iii)
(vi+1,ti+1)∈I
⟹
ta=ti+1
, and
(iv)
(vi+1,ti+1)∈O
⟹
ta≤ti+1≤ta+𝛥
.
If it is clear from context, then we write
(ti,ti+1)
-valid.
Note that if there exists a
(ti,ti+1)
-valid
𝛥
-restless temporal
(vi,vi+1)
-path
Pi+1
and
(ti+1,ti+2)
-valid
𝛥
-restless temporal
(vi+1,vi+2)
-path
Pi+2
, then we can “glue” them
together and get a
(ti,ti+2)
-valid
𝛥
-restless
(vi,vi+2)
-walk (not necessarily a path).
Thus if there exist a valid
𝛥
-restless temporal path between all consecutive pairs in a
𝛥
-ordering which are pairwise vertex disjoint (except for the endpoints), then there
exist a
𝛥
-restless temporal
(s,z)
-path.
The idea of Algorithm6.1 is that a
𝛥
-restless temporal
(s,z)
-path P induces a
valid partition of the timed feedback vertex set X such that
(v,t)∈I
if P arrives v
at time t,
(v,t)∈O
if P leaves v at time t, or otherwise
(v,t)∈U
. Furthermore, if
we order
M∶= I∪O∪ ({s,z}×{⊥})
according to the traversal of P (from s to z),
then this is a
𝛥
-ordering such that a subpath
P′
of P corresponding to consecutive
(v,t),(v�
,t�)∈M
with
v≠v′
is
(t,t�
,I,O)
-valid in some temporal graph
T′
of Line
(9), see Fig.6.
The algorithm tries all possible partitions of X and all corresponding
𝛥
-order-
ings. For each of these, we store the vertices
V(Pi)∩V(T)
in the family
Pi
, for all
valid
𝛥
-restless temporal
(vi−1,vi)
-path, where
(
v
i−1
,t),(v
i
,t
�)
are two consecutive
vertex appearances in the
𝛥
-ordering. Here, we assume without loss of general-
ity that no vertex appearance of s,z is in X. More specifically, for each two con-
secutive vertex appearances
(
v
i−1
,t),(v
i
,t
�)
in the
𝛥
-ordering our algorithm iterates
over all pairs of time edges leading from
(vi−1,t)
into the “forest” and from the
“forest” back to
(
v
i
,t
�)
. Since this fixes the entry points into the forest in each
iteration, any two
(ti,ti+1)
-valid
𝛥
-restless temporal
(vi,vi+1)
-paths present in the
iteration use the same vertices of the underlying graph. Hence it suffices to check
whether one exists. Note that, if we have
|Pi|≥0
for all
i∈{1, …,x+1}
, then
(a)
(b)
Fig. 6 Illustration of Algorithm6.1, where (a) depicts the set
({s,z}×{⊥}) ∪ I∪O
and (b) sketches the
underlying graph of the temporal graph
T
which is a forest. The back solid dots correspond to one or
two vertex appearances. The
𝛥
-restless temporal
(s,z)
-path is the red thick path which uses valid (Defini-
tion6)
𝛥
-restless temporal
(s,v1)
- and
(v1,v2)
-paths over
T
2790 Algorithmica (2021) 83:2754–2802
1 3
there is a
𝛥
-restless (s,z)-walk in
G
. Hence, to find a
𝛥
-restless temporal
(s,z)
-
path, we have to find
x+1
pair-wise disjoint sets
P(1)
1
,…,P
(x+1)
x+1
such that
Pi∈Pi
.
Here, we observe that the intersection graph in Line (12) is chordal [35] and use
an algorithm of Bentert etal.[10] for
choRDal multicoloReD inDepenDent set
as
a subroutine to find such pairwise-disjoint
P(1)
1
,…,P
(x+1)
x+1
.
Lemma 11 Algorithm6.1 runs in
O(6xx!x2
⋅
max{|G|3,|V|4})
time, if
x=|X|≤|V|
.
Proof Let
(G,s,z,X,𝛥)
be the input of Algorithm 6.1 and
x∶= |X|
. There are
at most
3x
many iterations of the loop in Line (1) and we can check in
O(|G|)
time whether a given partition
O⊎I⊎U=X
is valid. Since there are O(x!)
are many
𝛥
-orderings of
I⊎O⊎({s,z}×{⊥})
, the number of iterations of the
loop in Line (4) is also bounded by O(x!). Furthermore, we can check in
O(|G|)
time whether a given permutation
((
v
i
,t
i
))
|U⊎I|
i=1
of
U⊎I
is a
𝛥
-ordering where
s=v0,z=v|U⊎I|+1,t0=t|U⊎I|+1=⊥
. Note that during one iteration of the loop in
Line (4) we consider an time edge of
G
at most two times as
e1
and two times as
e2
in
Line (8). Hence, we have
O(|G|2)
many iteration of the loop in Line (8), during one
iteration of the loop in Line (4). Observe that Lemma1 implies that we can compute
a
𝛥
-restless temporal
(s,z)
-paths in linear time if the underlying graph is a forest.
Moreover, each
𝛥
-restless temporal
(vi−1,vi)
-path in
T′
departs at time t and arrives
at
t′
as
e1
and
e2
are in any temporal path from
vi−1
and
vi
. Hence, Line (11) can
be computed in
O(|G|)
time. Thus, we can compute Lines (5)–(11) in
O(|G|3)
time.
Observe that each set in
Pi
is either an empty set or contains the vertices of a path in
the forest
G↓(T)
, for all
i∈[x]
. Hence, the intersection graph G has at most
|V|2
⋅
x
vertices and is chordal. Thus, Line (14) can be computed in
O(3x|V|4
⋅
x2)
time with
an algorithm of Bentert et at.[10, Proposition5.6]. This gives an overall running
time of
O(6xx!
⋅
max{|G|3,|V|4x2})
.
◻
Lemma 12 Algorithm6.1 is correct.
Proof Let
G=(V,(Ei)i∈[
𝓁
])
be a temporal graph with
s,z∈V
and letX be a timed
feedback vertex set of
G
. We assume without loss of generalitythat s and z have no
vertex appearance in X, that is,
s,z∉{v∣(v,t)∈X}
. If this is not the case, then we
can add a new vertex
s
to
G
and for each edge
{s,v}∈Ei
, we add
{s,s}
to
Ei
. It is
clear that there exists a
𝛥
-restless temporal
(s,z)
-pathP if and only if there exists a
𝛥
-restless temporal
(s,z)
-path
P
. The set X remains a time feedback vertex set because
s
has degree one in the underlying graph
G↓
. Hence, we can now ask for a
𝛥
-restless
temporal
(s,z)
-path in
G
. The same holds for the vertex z by a symmetric argument.
We show now that Algorithm6.1 outputs yes if and only if there is a
𝛥
-restless
temporal
(s,z)
-path in
G
.
(⇒)
: We claim that if we find a multicolored independent set in (G,c), then there
is a
𝛥
-restless temporal
(s,z)
-path in
G=(V,(Ei)i∈[
𝓁
])
. Let
D
={P
(1)
1
,…,P
(x+1)
x+1}
be
such an multicolored independent set, let
(v0,t0)≤⋯≤(vx+1,tx+1)
be the respective
2791
1 3
Algorithmica (2021) 83:2754–2802
𝛥
-ordering when the setD was found, and let
I⊎O⊎X
be the valid partition ofX.
Hence,
Pi
represents a
(ti−1,ti,I,O)
-valid
𝛥
-restless temporal
(vi−1,vi)
-path. Due to D
being an independent set, it holds that
P(i)
i
∩P
(j)
j=�
for all
i≠j∈[x+1]
. For all
i∈[x+1]
it further holds that if
(vi,ti)∈I
, then
Pi−1
arrives in
vi
at time
ti
and
Pi
departs from
vi
not later thant with
ti≤t≤ti+𝛥
. If
(vi,ti)∈O
, then
Pi−1
arrives in
vi
at timet with
t≤ti≤t+𝛥
and
Pi
departs from
vi
at time
ti
. Hence,
Pi−1⋅Pi
is a
𝛥
-restless temporal
(vi−1,vi+1)
-path in
G
. Consequently,
P1⋯Px+1
is a
𝛥
-restless tem-
poral
(s,z)
-path in
G
.
(⇐)
: Assume
G
contains a
𝛥
-restless temporal
(s,z)
-path P, then let
I⊎O⊎U=X
be the partition of X that is induced by P. That is, for all
(v,t)∈I
there exists a time
edge (w,v,t) in P, for all
(v,t)∈O
there exists a time edge (v,w,t) in P, and for all
(v,t)∈U
there exist no time edge (v,w,t) or (w,v,t) in P. The partition
I⊎O⊎U
is a valid partition. Otherwise there exist two distinct vertex appearances
(v,t),(v,t�)∈O
such that there exist two time edges
(w,v,t),(u,v,t�)
in P indicating
that P visits the vertexv twice. The same argument works for two vertex appear-
ances of the same vertex in I. Let
(v1,t1)≤⋯≤(vx,tx)
be the vertex appearances in
the order in which they are visited by P. It holds that
t1≤…≤tx
and for
i<j∈[x]
if
vi=vj
, then there cannot exist a vertex appearance between
vi
and
vj
(otherwiseP
would visit
vi
twice). Thus
j=i+1
,
(vi,ti)∈I
,
(vj,tj)∈O
, and
ti≤tj≤ti+𝛥
. It
follows that
(s,⊥)=(v0,t0)≤(v1,t1)≤⋯≤(vx,tx)≤(vx+1,tx+1)=(z,⊥)
is a
𝛥
-ordering of
I⊎O⊎({s,z}×{⊥})
. Let
Pi
be the subpath of P starting in vertex
vi−1
and ending in
vi
for
i∈[x+1]
. If
vi−1=vi
, then it holds that
Pi
is empty and
Pi= {�}
(Line(7)). Otherwise, let
Pi
=(e(1)
i
=(v
i−
1,v(1)
i
,t(1)
i
),…,e
(p
i
)
i
=(v
(p
i
)
i
,v
i
,t
(p
i
)
i))
. Note
that if
(vi−1,ti−1)∈O
, then
t(1)
i
=t
i−1
; if
(vi−1,ti−1)∈I
, then
ti−1
≤t
(1)
i
≤t
i−1
+
𝛥
; if
(vi,ti)∈I
, then
t(p
i
)
i
=t
i
; and if
(vi,ti)∈O
, then
t(p
i
)
i
≤t
i
≤t
(p
i
)
i
+
𝛥
. Thus path
Pi
is a
(ti−1,ti,I,O)
-valid path in
T
+{e
(1)
i
,e
(p
i
)
i}
, and hence
V(Pi)⧵{vi−1,vi}∈Pi
(Line(11)).
Let
Qi=V(Pi)⧵{vi−1,vi}
. It holds that for
i≠j∈[x+1]
the paths
Pi
and
Pj
can
intersect only in their endpoints because P does not visit a vertex twice and
thus
Qi∩
Q
j=�
. For each
Pi
there exists a vertex
P(i)
i
in the intersection graphG
representing with
c
(P
(i)
i
)=
i
. For
i,j∈[x+1]
, there exist no edge
{
P
(i)
i
,P
(j)
j}
in G
because
Qi∩Qj=�
. Hence, G has a multicolored independent set
D
={P
(1)
1
,…,P
(x+1)
x+1}
of size
x+1
and Algorithm6.1 outputsyes.
◻
To conclude from Theorem8 the fixed-parameter tractability of
Restless tem
-
poRal path
parameterized the timed feedback vertex number, we need to compute a
timed feedback vertex set efficiently. This is clearly NP-hard, since it generalizes the
NP-complete
FeeDback VeRtex set
problem[43]. However, we establish the follow-
ing possibilities to compute a
FeeDback VeRtex set
.
Theorem9 A minimum timed feedback vertex set of temporal graph
G
can be com-
puted in
4x
⋅
|G|O(1)
time, where
x
is the timed feedback vertex number of
G
. Further-
more, there is a polynomial-time 8-approximation for timed feedback vertex set.
2792 Algorithmica (2021) 83:2754–2802
1 3
To prove Proposition9, we first show that a timed feedback vertex set of a tempo-
ral graph can be computed via the following problem.
Then the 8-approximation for timed feedback vertex set follows from the
8-approximation of Even etal. [27] for
WeighteD subset FeeDback set
.10 Now we
see two ways in the literature to deduce a FPT-algorithm for timed feedback ver-
tex set. One is via a reduction from sFVs-uV to the more general problem
gRoup
subset FeeDback VeRtex set
. The other is through Cygan etal.[22] who claim that
sFVs-uV is equivalent (under parameterized reductions for k) to
subset FeeDback
VeRtex set
. The latter is sFVs-uV where
V∞=�
. While the arguments of Cygan
etal.[22] only work if
V∞∩T=�
, we here provide the missing arguments to show
that the statement itself is true and hence fill a gap in the literature.
We start with the reduction to sFVs-uV.
Lemma 13 Given a temporal graph
G
and an integer
x∈ℕ
, we can construct in
O(|G|+|V|
𝓁
2)
time an instance
I=(G,V∞
,T,x)
of sFVs-UV such that I is a yes-
instance if and only if
G
has a timed feedback vertex set of size at most x.
Construction 1 Given a temporal graph
G=(V,(Ei)i∈[
𝓁
])
with underlying graph
G↓=(V,E)
, we construct the instance
I=(G=(V�
,E�),V∞
,T,x)
of
subset FeeD
-
back VeRtex set With unDeletable VeRtices
, where
V�
∶=
⋃v∈V
V
v
∪
⋃e∈E
∪V
e
and
E�
∶=
⋃v∈V
Ev∪
⋃e∈E
Ee∪
⋃t∈[
𝓁
]⋃e∈Et
E(e,t
)
. Here,
Finally we set
V∞
∶=
⋃e∈E
∪V
e
. Consider Fig.7 for an example.
⧫
∀v∈V∶V
v
∶= {v
i
∣i∈[𝓁],v∈e,e∈E
i
},
∀e={u,w}∈E∶Ve∶= {e(u),e(T),e(w)},
T∶= {e(T)∣e={u,w}∈E},
∀v∈V∶Ev∶= {{vi,vj}∣vi,vj∈Vv,vi≠vj},
∀e={u,w}∈E∶Ee∶= {{e(u),e(T)},{e(T),e(w)}}, and
∀
t∈[𝓁],∀e={u,w}∈E
t
∶E
(e,t)
∶= {{e(u),u
t
},{w
t
,e(w)}∣u
t
∈V
u
,w
t
∈V
w
}
.
10 There is a straightforward reduction from sFVs-uV to
WeighteD subset FeeDback set
using infinite
weights.
2793
1 3
Algorithmica (2021) 83:2754–2802
Proof of Lemma 13 Let
G=(V,E1,…,E
𝓁
)
be a temporal graph,
x∈ℕ
, and
I=(G,V∞
,T,x)
be the resulting instance from Construction1. It is easy to check
that Construction1 can be computed in
O(|G|+|V|
𝓁
2)
time.
We now claim that there is a timed feedback vertex set X of size at most x in
G
if and only if there is a subset feedback vertex X of size at most x in G such that
X∩V∞=�
.
(⇒)
: Let X be a timed feed back vertex for
G
. Then, set
Y∶= {vt∈Vv∣(v,t)∈X}
.
Hence,
|Y|≤x
and
Y∩V∞=�
. We claim that Y is a subset feedback vertex set for
I. Assume towards a contradiction that there is a simple cycle C in
G−Y
which
contains a vertex of T. Furthermore, we assume without loss of generality that there
is no shorter cycle in
G−Y
which contains a vertex of T. Observe that this implies
that C does not visit three distinct vertices
va,vb,vc∈Vv
, for any
v∈V
, because
otherwise there is a shorter cycle using one of the edges
{va,vb}
,
{va,vc}
or
{vc,vb}
in
Ev
. Moreover if C visits two distinct vertices
va,vb∈Vv
, then
{va,vb}∈Ev
is part
of C, for all
v∈V
, because otherwise there is a shorter cycle using the edge
{va,vb}
.
Furthermore, for all edge
e∈E
we have that
Ve⊆V(C)
or
Ve∩V(C)=�
, because
G[Ve]
induces a
P3
and hence using only an endpoint of that
P3
would imply that
C visits two vertices
va,vb∈Vv
without the edge
{va,vb}
, for some
v∈V
. Since T
only contains the middle vertex
e(T)
∈E
e
of the
P3
induced by
G[Ve]
, we can observe
that C is a subdivision of a cycle in
G
↓
(G−X)
which contradicts that X is a timed
feedback vertex set for
G
.
(⇐)
: Let
Y⊆(V�⧵V∞)
be of size at most x such that no simple cycle in
G�−X
which contains a vertex in T. We set
X
∶= {(v,t)∣v
t
∈
⋃u∈V
V
u
∩Y
}
. Hence, X is
of size at most x. We claim that X is a timed feedback vertex set for
G
. Assume
towards a contradiction that this is not the case and there is a cycle C in
G
↓
(G−X)
.
We now build a cycle in
G−Y
containing a vertex from T. Note that for each edge
e used in C none of the vertices in
Ve
are in Y, otherwise
V∞∩Y≠�
. Hence, set
VC
∶=
⋃e∈E(C)
E
e
, where E(C) is the edge set of C. Since any two incident edges
Fig. 7 An illustration of Construction1 for a temporal graph
G
(left) to graph G (right). The set
Vu
in G
of a vertexu in
G
is depicted by a large circle. The vertices in
Ve
of an edgee in the underlying graph of
G
are filled. The vertices inT are squared (red)
2794 Algorithmica (2021) 83:2754–2802
1 3
e1,e2∈E(C)
are in the underlying graph of
G−X
, we know that there are
t1,t2∈[𝓁]
such that
(e1,t1)
and
(e2,t2)
are time edges of
G−X
. Hence, for two incident edges
e1,e2∈E(C)
with
{v}=e1∩e2
we pick
t1,t2∈[𝓁]
such that
(e1,t1)
and
(e2,t2)
are
time edges of
G−X
add
vt1,vt2
∈Vv
to
VC
. Observe that
G[VC]
contains a cycle and
that
VC∩T≠�
. Since we constructed
VC
from a cycle in the underlying graph of
G−X
we have
VC∩Y=�
. This is a contradiction.
◻
Now we can use the polynomial-time 8-approximation of Even et al. [27] for
WeighteD subset FeeDback VeRtex set
and Lemma13 to conclude the following.11
Corollary 4 There is a polynomial-time 8-approximation for timed feedback vertex
set.
In the remainder of this section we prove the following.
Lemma 14 Given an instance
I=(G,V∞
,T,k)
of
sUbset Feedback VeRtex set
wIth Undeletable VeRtIces
we can construct in
O(k2(|V|+|E|))
time an instance
I�=(G,T�
,k�)
of
sUbset Feedback VeRtex set
with
k′≤k
such that I is a yes-
instance if and only if
I′
is a yes-instance.
Note that the running time of the algorithm behind Lemma14 depends only
linearly on the size of the graph. The proof of Lemma14 is deferred to the end
of this section. First, we introduce two data reductions rules and then perform the
reduction behind Lemma14 in two steps. We use these data reduction rules to get
an equivalent instance where
G[T∩V∞]
is an independent set. We start by detect-
ing some no-instances.
Reduction Rule 2 Let
I=(G,V∞
,T,k)
be an instance of
subset FeeDback VeR
-
tex set With unDeletable VeRtices
such that there is a vertex u and a simple
cycle C intersecting T where
V(C)⧵(T∩V∞)⊆{u}⊆V∞
. Then output a trivial
no-instance.
We now show that we can detect in linear-time whether ReductionRule2 is
applicable and that it is safe. The latter means that the application of Reduc-
tionRule2 does not turn a yes-instance into a no-instance or vice versa.
Lemma 15 ReductionRule2 is safe and can be applied in linear time.
Proof Since C is a witness that I is a no-instance, ReductionRule2 is safe. We check
whether there is cycle C such that
V(C)⧵(T∩V∞)=�
by simply checking whether
G[T∩V∞]
is a forest. Assume that
G[T∩V∞]
is a forest, otherwise we are done
and output a trivial no-instance. First, we partition
V(G[T∩V∞]) = Q1⊎⋯⊎Qc
11 Here, vertices get weight
∞
if there are undeletable, and one otherwise.
2795
1 3
Algorithmica (2021) 83:2754–2802
such that
Qi
is a maximal connected component of
G[T∩V∞]
. Clearly, this can be
done in linear time. For each connected component
Qi
of
G[T∩V∞]
we first unmark
all vertices in
V⧵(T∩V∞)
. Then we iterate over all vertices
v∈Qi
and mark all
vertices in
NG(v)∩(V∞⧵T)
. If we find a vertex
w∈Qi
such that there is a ver-
tex
u∈NG(w)∩(V∞⧵T)
which is already marked, then the path from v to w in
Qi
together with u is a cycle C where
V(C)⧵(T∩V∞)⊆{u}⊆V∞
. Hence, we output
a trivial no-instance in this case. Moreover, if there is some simple cycle C where
V(C)⧵(T∩V∞)⊆{u}⊆V∞
, then all vertices
V(C)⧵{u}
belong to the same con-
nected component of
G[T∩V∞]
. Thus, the above described procedure will find C.
A simple application of the Handshaking Lemma shows that this procedure ends
after linear time.
◻
The purpose of the next data reduction rule is to merge undeletable terminal
vertices which do share an edge.
Reduction Rule 3 Let
I=(G,V∞
,T,k)
be an instance of
sub
-
set FeeDback VeRtex set With unDeletable VeRtices
such that there is
{v,w}∈E
with
{v,w}⊆T∩V∞
and
NG(v)∩NG(w)∩V∞=�
. Then set
G=(V(G−w),E(G−w)∪{{v,u}∣{w,u}∈E})
and
G
�∶=
G−(N
G
(v)∩N
G
(w
))
.
Output
I�
=(G
�
,V
∞
∩V(G
�
),T∩V(G
�
),k−
|
N
G
(v)∩N
G
(w)
|)
.
Note that for each edge in
G[T∩V∞]
, either Reduction Rule 2 or Reduc-
tionRule3 is applicable. While it is easy to apply ReductionRule3 exhaustively
in polynomial time, more effort is required to do the same in linear time. To this
end, we will construct in linear time an equivalent instance such that Reduc-
tionRules2 and 3 are not applicable.
Lemma 16 Given an instance I of
sUbset Feedback VeRtex set wIth Undeletable
VeRtIces
, we can compute an equivalent instance
I′
of
sUbset Feedback VeRtex set
wIth Undeletable VeRtIces
in linear time such that ReductionRules2 and 3 are not
applicable to
I′
.
Proof We first check in linear time by Lemma 15 whether Reduction Rule 2 is
applicable. Assume that ReductionRule2 is not applicable, otherwise we are done.
Hence,
G[T∩V∞]
is a forest.
We now aim to apply ReductionRule3 for all edges in
G[T∩V∞]
at once. First,
we partition
V(G[T∩V∞]) = Q1⊎⋯⊎Qc
such that
Qi
is a maximal connected
component of
G[T∩V∞]
. Then we replace
Qi
with a fresh vertex
qi
. To this end, we
construct the graph
G�∶= (V�
,E�)
where
Note that
G′
and hence
V�∞ =(V∞∩V�)∪{qi∣i∈[c]}
and
T�=(T∩V�)∪{qi∣i∈[c]}
can be computed in linear time. To compute the
V�
∶=(V
⧵
(T∩V
∞
))∪{qi∣i∈[c]} and
E
�
∶={{a,b}∈E∣{a,b}⊆V
�
}∪{{qi,w}∣w∈V
�
and ∃v∈Qi∶{v,w}∈E}.
2796 Algorithmica (2021) 83:2754–2802
1 3
remaining budget
k′
, we set
K=�
. Then, for each connected component
Qi
of
G[T∩V∞]
, we first unmark all vertices. Second, we iterate over all vertices
v∈Qi
and mark all vertices in
NG(v)⧵(T∩V∞)
. If we find a vertex
w∈Qi
such that a
vertex
u∈NG(w)⧵(T∩V∞)
which is already marked, then we add u toK, because
G[Qi∪{u}]
contains a cycle intersecting T where u is the only deletable vertex.
Recall that
u∉V∞
, since ReductionRule2 was not applicable. A simple applica-
tion of the Handshaking Lemma show that this procedure ends after linear time. If
k<|K|
, then we return a trivial no-instance, because for each vertex
v∈K
there is
a simple cycle intersecting T where v is the unique vertex not in
V∞∩T
. Otherwise,
we output
I�=(G�−K,V�∞
,T�⧵K,k�=k−|K|)
. It is easy to verify that Reduc-
tionRule3 is not applicable in
I′
. We now claim that I is a yes-instance if and only if
I′
is a yes-instance.
(⇒)
: Assume that X is a solution for I. Note that for each vertex
v∈K
, there is
a simple cycle intersecting T where v is the unique vertex not in
V∞∩T
. Hence,
K⊆X
. Set
X�∶= X⧵K
and observe that
X�⊆V(G�)
. The set
X′
is a solution for
I′
, because it is of size at most
k′
and for each cycle in
G�−K
which intersects to
T′⧵K
, we can construct a cycle in G which intersects to T by replacing a vertex
qj∈{qi∣i∈[c]}
with a path in
G[Qj]
.
(⇐)
: Assume that
X′
is a solution for
I′
. We set
X∶= X�∪K
and note that X is of
size at most k. We may assume towards a contradiction that X is not a solution for
I. Hence there is a simple cycle C in
G−X
which contains a vertex of T. We now
construct a closed walk of
C′
in
G�−T
from C by replacing a subpath on vertices in
Qi
with
qi
, for all
i∈[c]
. Since we only replaced vertices from
T∩V∞
of I with ver-
tices in
T�∩V�∞
, the closed walk
C′
contains a simple cycle in
G�−X�
containing a
vertex from
T′
—a contradiction.
◻
We now show an algorithm to dispose all vertices undeletable vertices in T
such that the running time dependence only linearly on the size of the graph.
Lemma 17 Let
I=(G,V∞
,T,k)
be an instance of
sUbset Feedback VeRtex set
wIth Undeletable VeRtIces
. We can construct in
O(k(|V|+|E|))
time an instance
I�=(G�
,V�∞
,T�
,k�)
of
sUbset Feedback VeRtex set wIth Undeletable VeRtIces
such
that
1.
k′≤k
,
2.
V�∞ ⧵T�=�
,
3. I is a yes-instance if and only if
I′
is a yes-instance.
Proof Let
I=(G,V∞
,T,k)
be an instance of
subset FeeDback VeRtex set With
unDeletable VeRtices
. Since we aim for a running time of
O(k(|V|+|E|))
, we can
assume that ReductionRules2 and 3 are not applicable on I, see Lemma16.
2797
1 3
Algorithmica (2021) 83:2754–2802
The goal now is to duplicate each vertex in
V∞⧵T
k+1
times, such that we can-
not delete all of them even if there are not in
V∞
. Note that we might create many
copies of an edge doing this naïvely. To avoid this, we observe that it suffices to
replace each maximal connected component in
G[V∞⧵T]
with
k+1
vertices. We
partition
V(G[V∞⧵T]) = Q1⊎⋯⊎Qc
such that
Qi
is a maximal connected compo-
nent of
G[V∞⧵T]
and we construct
G�∶= (V�
,E�)
, where
Since
|
{q
j
i
∣i∈[c],j∈[k+1]}
|
≤
|
V
|
(k+1
)
and we copy each edge at most
k+1
times,
G′
is constructed after
O(k(|V|+|E|))
time.
We now claim that I is a yes-instance if and only if
I�∶= (G�
,T�∶= V∞∩V(G�),T,k)
is a yes-instance of
subset FeeDback VeRtex set
With unDeletable VeRtices
.
(⇒)
: Let X be a solution for I. Then X is also a solution for
I′
, because
X∩V∞=�
and for each cycle
C′
in
G′
containing a vertex from T, we can construct a closed
walk in G by replacing a vertex
qj
i
by a path in
G[Qi]
. This closed walk induces a
simple cycle C in G containing a vertex in T. Hence,
C′
also contains a vertex from
X.
(⇐)
: Let X be a solution for
I′
. We assume without loss of generality that
X
∩{q
j
i
∣i∈[c],j∈[k+1
]}=�
. Suppose towards a contradiction that X is not a
solution for I. Let C be an cycle in G satisfying
V(C)∩X=�≠V(C)∩T
.
We construct a closed walk
C′
in
G′
from C by replacing each maximal consecu-
tive subpath in C containing only vertices from
Qi
with
q1
i
, for all
i∈[c]
. Note that C
contains a simple cycle which intersects
T′
but not X—a contradiction.
◻
Now we are finally ready to prove Lemma14.
Proof of Lemma 14 First, we apply Lemma 17 on I and hence assume that
V∞⧵T=�
. Furthermore, by Lemma16 we assume that ReductionRules3 and 2
are not applicable. Thus,
G[V∞∩T]
is an independent set. We now create
k+1
cop-
ies of each vertex in
V∞∩T
such that we cannot remove all of them, even if there
are deletable. However, we have to be careful what kind of new cycles this creates.
We do the following. Let
V∞∩T={v1,v2,…,vp}
and take a fresh set of vertices
Qi
∶= {q
j
i
∣j∈[k+1
]}
for each
i∈[p]
. We construct
G�∶= (V�
,E�)
, where
V�
∶= (V⧵(V
∞
⧵T))∪{q
j
i∣i∈[c],j∈[k+1]} and
E
�∶= E(G[V⧵(V∞⧵T)]) ∪ {{qj
i
,w}∣∃v∈Q
i
∶{v,w}∈E}
.
2798 Algorithmica (2021) 83:2754–2802
1 3
Output
I�=(G�
,T�
,k)
, where
T�∶= (
T
⧵
V
∞)∪{
w
i∣{
v
i,
w
}∈
E
}
. Since
|
{q
j
i
∣i∈[c],j∈[k+1]}
|≤|
V
|
(k+1
)
and we create for each edge at most
k+2
new edges,
G′
is constructed after
O(k(|V|+|E|))
time. Together with the preproc-
essing of Lemma17 this gives an overall running time of
O(k2(|V|+|E|))
.
We now claim that I is a yes-instance if and only if
I′
is a yes-instance of
subset
FeeDback VeRtex set
.
(⇒)
: Let X be a solution for I. Observe that
X⊆V′
, because
V⧵V�⊆V∞
.
Assume towards a contradiction that there is a cycle
C′
in
G′
such that
V(C�)∩X=�
.
Assume without loss of generality that
C′
is a shortest of the set of cycles satisfy-
ing
V(C�)∩X=�
. Hence, for each
i∈[p]
we have that
|
V
(
C
�)∩
Q
i|≤1
, and since
G[V∞∩T]
is an independent set, a vertex
qj
i
∈V(C�)∩Q
i
has two neighbors
w′
i
,u
′
i
,
where
w,u∈V
. Thus, we can construct a cycle C in G by replacing each subpath
w
′
i
,q
j
i
,u
′
i
with the vertex
vi∈T∩V∞
, where
qj
i
∈V(C�)∩Q
i
and
i∈[p],j∈[k+1]
.
This contradicts X being a solution forI.
(⇐)
: Let
X′
be a solution for
I′
. For all
i∈[p]
, we assume without loss of general-
ity that
X�
∩Q
i=�
: This can be assumed, because
|
Q
i|>
k
≥|
X
′|
and all
vertices in
Qi
have the same neighborhood.
X�
∩{w
i
∣{v
i
,w}∈E
}=�
: This can be assumed, because these vertices are of
degree two and thus a vertex
wi
can be replaced by its
origin w.
X�
∩{w
�
i
∣{v
i
,w}∈E
}=�
: Such a vertex
w′
i
can be replaced by its origin w as
well, because for each cycle
C′
in
G′
passing through
T′
which does not include w, we know that
v
′
i
q
j
i
w′
i
q
j′
i
u
′
i
is a subpath of
C′
for some
v,u∈V
,
qj
i
,q
j�
i
∈Q
i
, and
j,j�∈[k+1]
. Hence
C
�−{q
j
i
,w
i}
is also a cycle
in
G′
that contains a vertex from
T′
. Thus, there is
V
(C
�
)∩(X
⧵
{w
�
i
})
≠�
.
Hence
X�⊆V⧵V∞
. Now assume towards a contradiction that there is a cycle C in
G which does not contain a vertex in
X′
. Hence there
vi∈V(C)∩(T∩V∞)
, other-
wise C is also a cycle in
G′
. We construct a cycle
C′
in
G′
from C by replacing each
subpath
u,vi,w
in C with
u
,u
i
,u
′
i
,v
i
,w
′
i
,w
i
,
w
, for all
vi∈V(C)∩(T∩V∞)
. This
contradicts
X′
being a solution because
ui∈
T
�
.
◻
V
�∶=(V⧵(V∞∩T)) ∪
p
⋃
i=1
Qi∪{w�
i,wi∣{vi,w}∈E}, and
E
�∶={{v,w}∈E∣v,w∈V�}∪
{{w
i
,w},{w
i
,w�
i
},{w�
i
,qj
i
}∣{v
i
,w}∈E,i∈[p]},j∈[k+1]}
.
2799
1 3
Algorithmica (2021) 83:2754–2802
By using Lemmas13 and 14 we now can compute a minimum timed feedback
vertex set by any known
subset FeeDback VeRtex set
algorithms. Thus, Lem-
mas13 and 14 and Corollary4 together with the algorithm of Iwata etal.[42] imply
Proposition9.
7 Conclusion
We have analyzed the (parameterized) computational complexity of
Restless tem
-
poRal path
, a canonical variant of the problem of finding temporal paths, where
the waiting time at every vertex is restricted. Unlike its non-restless counterpart or
the “walk-version”, this problem turns out to be computationally hard, even in quite
restricted cases. On the positive side, we give an efficient algorithm to find short
restless temporal paths and we could identify structural parameters of the underlying
graph and of the temporal graph itself that allow for fixed-parameter algorithms.
Acknowledgements We thank the referees for their careful reading and constructive comments which
significantly improved the presentation of these results.
Funding Open Access funding enabled and organized by Projekt DEAL.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License,
which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as
you give appropriate credit to the original author(s) and the source, provide a link to the Creative Com-
mons licence, and indicate if changes were made. The images or other third party material in this article
are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the
material. If material is not included in the article’s Creative Commons licence and your intended use is
not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission
directly from the copyright holder. To view a copy of this licence, visit http:// creat iveco mmons. org/ licen
ses/ by/4. 0/.
References
1. Akanksha, A., Pallavi, J., Lawqueen, K., Saket, S.: Parameterized complexity of conflict-free match-
ings and paths. Algorithmica 82, 1939–1965 (2020)
2. Aigner, M., Ziegler, G.M., Hofmann, K.H., Paul ErdosPaul ErdosErdos, P.: Proofs from the Book.
Springer, Berlin (2010)
3. Akrida, E.C., Gąsieniec, L., Mertzios, G.B., Spirakis, P.G.: The complexity of optimal design of
temporally connected graphs. Theory Comput. Syst. 61(3), 907–944 (2017)
4. Akrida, E.C., Czyzowicz, J., Gąsieniec, L., Kuszner, Ł., Spirakis, P.G.: Temporal flows in temporal
networks. J. Comput. Syst. Sci. 103, 46–60 (2019)
5. Akrida, E.C., Mertzios, G.B., Nikoletseas, S., Raptopoulos, C., Spirakis, P.G., Zamaraev, V.: How
fast can we reach a target vertex in stochastic temporal graphs? J. Comput. Syst. Sci. 114, 65–83
(2020)
6. Alman, J., Williams, V.V.: A refined laser method and faster matrix multiplication. In: Proceedings
of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA ’21), pp. 522–539. SIAM
(2021)
7. Axiotis, K., Fotakis, D.: On the size and the approximability of minimum temporally connected
subgraphs. In: Proceedings of the 43rd International Colloquium on Automata, Languages, and Pro-
gramming (ICALP’16), pp. 149:1–149:14 (2016)
2800 Algorithmica (2021) 83:2754–2802
1 3
8. Barabási, A.-L.: Network Science. Cambridge University Press, Cambridge (2016)
9. Bentert, M., Dittmann, A., Kellerhals, L., Nichterlein, A., Niedermeier, R.: An adaptive version of
Brandes’ algorithm for betweenness centrality. In: 29th International Symposium on Algorithms and
Computation, ISAAC 2018, December 16–19, 2018, Jiaoxi, Yilan, Taiwan, pp. 36:1–36:13 (2018)
10. Bentert, M., van Bevern, R., Niedermeier, R.: Inductive
k
-independent graphs and
c
-colorable sub-
graphs in scheduling: a review. J. Sched. 22(1), 3–20 (2019)
11. Bentert, M., Himmel, A.-S., Nichterlein, A., Niedermeier, R.: Efficient computation of optimal tem-
poral walks under waiting-time constraints. Appl. Netw. Sci. 5(1), 1–26 (2020)
12. Berman, K.A.: Vulnerability of scheduled networks and a generalization of Menger’s theorem.
Netw. An Int. J. 28(3), 125–134 (1996)
13. van Bevern, R., Mnich, M., Niedermeier, R., Weller, M.: Interval scheduling and colorful independ-
ent sets. J. Sched. 18(5), 449–469 (2015)
14. Bhadra, S., Ferreira, F.: Complexity of connected components in evolving graphs and the computa-
tion of multicast trees in dynamic networks. In: International Conference on Ad-Hoc Networks and
Wireless, pp. 259–270. Springer (2003)
15. Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition.
SIAM J. Discrete Math. 28(1), 277–305 (2014)
16. Briggs, P., Torczon, L.: An efficient representation for sparse sets. ACM Lett. Program. Lang. Syst.
(LOPLAS) 2(1–4), 59–69 (1993)
17. Bui-Xuan, B.-M., Ferreira, A., Jarry, A.: Computing shortest, fastest, and foremost journeys in
dynamic networks. Int. J. Found. Comput. Sci. 14(02), 267–285 (2003)
18. Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic net-
works. Int. J. Parallel Emerg. Distrib. Syst. 27(5), 387–408 (2012)
19. Casteigts, A., Flocchini, P., Godard, E., Santoro, N., Yamashita, M.: On the expressivity of time-
varying graphs. Theor. Comput. Sci. 590, 27–37 (2015)
20. Casteigts, A., Peters, J., Schoeters, J.: Temporal cliques admit sparse spanners. In: Proceedings of
the 46th International Colloquium on Automata, Languages, and Programming (ICALP’19), vol-
ume 132 of LIPIcs, pp. 134:1–134:14. Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2019)
21. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Lon-
don (2009)
22. Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Subset feedback vertex set is fixed-
parameter tractable. SIAM J. Discrete Math. 27(1), 290–309 (2013)
23. Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Pilipczuk, M., Saurabh, S., Marx, D., Pilipc-
zuk, M.: Parameterized Algorithms. Springer, Berlin (2015)
24. Diestel, R.: Graph Theory, 5th edn, volume 173 of Graduate Texts in Mathematics. Springer, Berlin
(2016)
25. Eames, K.T.D., Keeling, M.J. (2003) Contact tracing and disease control. Proc. R. Soc. Lond. Ser. B
Biol. Sci. 270(1533):2565–2571
26. Enright, J., Meeks, K., Mertzios, G., Zamaraev, V.: Deleting edges to restrict the size of an epi-
demic in temporal networks. In: Proceedings of the 44th International Symposium on Mathe-
matical Foundations of Computer Science (MFCS’19), volume 138 of LIPIcs, pp. 57:1–57:15.
Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2019)
27. Even, G., Naor, J., Zosin, L.: An 8-approximation algorithm for the subset feedback vertex set
problem. SIAM J. Comput. 30(4), 1231–1252 (2000)
28. Fellows, M.R., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of
multiple-interval graph problems. Theor. Comput. Sci. 410(1), 53–61 (2009)
29. Ferretti, L., Wymant, C., Kendall, M., Zhao, L., Nurtay, A., Abeler-Dörner, L., Parker, M., Bon-
sall, D., Fraser, C.: Quantifying SARS-CoV-2 transmission suggests epidemic control with digi-
tal contact tracing. Science (2020)
30. Fluschnik, T., Molter, H., Niedermeier, R., Renken, M., Zschoche, P.: Temporal graph classes: a
view through temporal separators. Theor. Comput. Sci. 806, 197–218 (2020)
31. Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.. Efficient computation of representative
families with applications in parameterized and exact algorithms. J. ACM 63(4):29:1–29:60
(2016)
32. Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Representative families of product fami-
lies. ACM Trans. Algorithms 13(3), 36:1–36:29 (2017)
33. Fortune, S., Hopcroft, J.E., Wyllie, J.: The directed subgraph homeomorphism problem. Theor.
Comput. Sci. 10, 111–121 (1980)
2801
1 3
Algorithmica (2021) 83:2754–2802
34. Fredman, M.L., Willard, D.E.: Blasting through the information theoretic barrier with
fusion trees. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing
(STOC’90), pp. 1–7 (1990)
35. Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Combin.
Theory Ser. B 16(1), 47–56 (1974)
36. Haag, R., Molter, H., Niedermeier, R., Renken, M.: Feedback edge sets in temporal graphs. In:
Proceedings of the 46th International Workshop on Graph-Theoretic Concepts in Computer Sci-
ence (WG’20), volume 12301 of Lecture Notes in Computer Science, pp. 200–2012. Springer
(2020)
37. Holme, P.: Modern temporal network theory: a colloquium. Eur. Phys. J. B 88(9), 234 (2015)
38. Holme, P.: Temporal network structures controlling disease spreading. Phys. Rev. E 94(2), 022305
(2016)
39. Holme, P., Saramäki, J. (eds.): Temporal Network Theory. Springer, Berlin (2019)
40. Impagliazzo, R., Paturi, R.: On the complexity of
k
-SAT. J. Comput. Syst. Sci. 62(2), 367–375
(2001)
41. Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J.
Comput. Syst. Sci. 63(4), 512–530 (2001)
42. Iwata, Y., Wahlström, M., Yoshida, Y.: Half-integrality, LP-branching, and FPT algorithms. SIAM
J. Comput. 45(4), 1377–1411 (2016)
43. Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computa-
tions, pp. 85–103. Springer, Berlin (1972)
44. Kempe, D., Kleinberg, J., Kumar, A.: Connectivity and inference problems for temporal networks. J.
Comput. Syst. Sci. 64(4), 820–842 (2002)
45. Kermack, W.O., McKendrick, A.G.: A contribution to the mathematical theory of epidemics. Proc.
R. Soc. Lond. Ser. A 115(772), 700–721 (1927)
46. Latapy, M., Viard, T., Magnien, C.: Stream graphs and link streams for the modeling of interactions
over time. Soc. Netw. Anal. Min. 8(1), 61 (2018)
47. Lokshtanov, D., Misra, P., Panolan, F., Saurabh, S.:. Deterministic truncation of linear matroids.
ACM Trans. Algorithms 14(2), 14:1–14:20 (2018a)
48. Lokshtanov, D., Misra, P., Panolan, F., Saurabh, S., Zehavi, M.: Quasipolynomial representation of
transversal matroids with applications in parameterized complexity. In: Proceedings of the 9th Inno-
vations in Theoretical Computer Science Conference (ITCS’18), pp. 32:1–32:13 (2018b)
49. Marx, D.: A parameterized view on matroid optimization problems. Theor. Comput. Sci. 410(44),
4471–4479 (2009)
50. Mertzios, G.B., Michail, O., Spirakis, P.G.: Temporal network optimization subject to connectivity
constraints. Algorithmica 81(4), 1416–1449 (2019)
51. Michail, O.: An introduction to temporal graphs: an algorithmic perspective. Internet Math. 12(4),
239–280 (2016)
52. Molter, H.: Classic graph problems made temporal—a parameterized complexity analysis.
Ph.D. thesis, Technische Universität Berlin, December 2020. http:// dx. doi. org/ 10. 14279/ depos
itonce- 10551
53. Nešetřil, J., Mendez, P.O. De.: Sparsity: Graphs, Structures, and Algorithms. Springer, Berlin
(2012)
54. Newman, M.E.J.: Networks. Oxford University Press, Oxford (2018)
55. Oxley, J.G.: Matroid Theory. Oxford University Press, Oxford (1992)
56. Pan, R.K., Saramäki, J.: Path lengths, correlations, and centrality in temporal networks. Phys. Rev. E
84(1), 016105 (2011)
57. Sorge, M., Weller, M. etal.: The graph parameter hierarchy, 2018. https:// manyu. pro/ assets/ param
eter- hiera rchy. pdf (2020)
58. Tao, T., CrootIII, E., Helfgott, H.: Deterministic methods to find primes. Math. Comput. 81(278),
1233–1246 (2012)
59. Tovey, C.A.: A simplified NP-complete satisfiability problem. Discret. Appl. Math. 8(1), 85–89
(1984)
60. Williams, R.: Finding paths of length
k
in
O∗(
2
k)
time. Inf. Process. Lett. 109(6), 315–318 (2009)
61. Wu, H., Cheng, J., Ke, Y., Huang, S., Huang, Y., Wu, H.: Efficient algorithms for temporal path
computation. IEEE Trans. Knowl. Data Eng. 28(11), 2927–2942 (2016)
62. Zschoche, P., Fluschnik, T., Molter, H., Niedermeier, R.: The complexity of finding separators in
temporal graphs. J. Comput. Syst. Sci. 107, 72–92 (2020)
2802 Algorithmica (2021) 83:2754–2802
1 3
Authors and Affiliations
ArnaudCasteigts1· Anne‑SophieHimmel2· HendrikMolter2·
PhilippZschoche2
Arnaud Casteigts
arnaud.casteigts@labri.fr
Anne-Sophie Himmel
[email protected]
Hendrik Molter
[email protected]
1 LaBRI, CNRS, Bordeaux INP, Université de Bordeaux, Bordeaux, France
2 Algorithmics andComputational Complexity, Technische Universität Berlin, Berlin, Germany
Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published
maps and institutional affiliations.