Università degli studi di Bergamo<EMAIL_ADDRESS>Universit de
Sherbrooke<EMAIL_ADDRESS>[500]Theory of computation
Design and analysis of algorithms [500]Theory of computation Parameterized
complexity and exact algorithms [500]Theory of computation Graph algorithms
analysis

###### Acknowledgements.

… 1

# An FTP Algorithm for Temporal Graph Untangling

Riccardo Dondi  Manuel Lafond

###### Abstract

Several classical combinatorial problems have been considered and analysed on
temporal graphs. Recently, a variant of Vertex Cover on temporal graphs,
called MinTimelineCover, has been introduced to summarize timeline activities
in social networks. The problem asks to cover every temporal edge while
minimizing the total span of the vertices (where the span of a vertex is the
length of the timestamp interval it must remain active in, minus one). While
the problem has been shown to be NP-hard even in very restricted cases, its
parameterized complexity has not been fully understood. The problem is known
to be in FPT under the span parameter only for graphs with two timestamps, but
the parameterized complexity for the general case is open. We settle this open
problem by giving an FPT algorithm that is based on a combination of iterative
compression and a reduction to the Digraph Pair Cut problem, a powerful
problem that has received significant attention recently.

###### keywords:

Temporal Graphs, Vertex Cover, Graph Algorithms, Parameterized Complexity

###### category:

##  1 Introduction

Temporal graphs are emerging as one of the main models to describe the
dynamics of complex networks. They describe how relations (edges) change in in
a discrete time domain [11, 10], while the vertex set is not changing. The
development of algorithms on temporal graphs has mostly focused on finding
paths or walks and on analyzing graph connectivity [11, 19, 20, 6, 21, 7, 3,
16, 1, 5]. However, several classical problems in computer science have been
recently extended to temporal graphs and one of the most relevant problem in
graph theory and theoretical computer science, Vertex Cover, has been
considered in this context [2, 9, 18].

In particular, here we study a variant of Vertex Cover, called Network
Untangling introduced in [18]. Network Untangling has application in
discovering event timelines and summarizing temporal networks. It considers a
sequence of temporal interactions between entities (e.g. discussions between
users in a social network) and aims to explain the observed interactions with
few (and short) _activity intervals_ of entities, such that each interaction
is covered by at least one of the two entities involved (i.e. at least one of
the two entities is active when an interaction between them is observed).

Network Untangling can be seen as a variant of Vertex Cover, where we search
for a minimum cover of the interactions, called temporal edges. The size of
this temporal vertex cover is based on the definition of _span_ of a vertex,
that is the length of vertex activity. In particular, the span of a vertex is
defined as the difference between the maximum and minimum timestamp where the
vertex is active. Hence, if a vertex is active in exactly one timestamp, it
has a span equal to $0$.

Four combinatorial formulations of Network Untangling have been defined in
[18], varying the definition of vertex activity (a single interval or $h\geq
2$ intervals) and the objective function (minimization of the sum of vertex
spans or minimization of the maximum vertex span). Here we consider the
formulation, denoted by MinTimelineCover, where vertex activity is defined as
a single interval and the objective function is the minimization of the sum of
vertex spans. Hence, given a temporal graph, MinTimelineCover searches for a
cover of the temporal edges that has minimum span and such that each vertex is
active in one time interval.

The MinTimelineCover problem is known to be NP-hard [18]. The problem is hard
also in very restricted cases when each timestamp contains at most one
temporal edge [4], when each vertex has at most two incident temporal edges in
each timestamp and the temporal graph is defined over three timestamps [4],
and when the temporal graph is defined over two timestamps [8]. Note that,
since the span of a vertex activity in exactly one timestamp is equal to $0$,
MinTimelineCover is trivially in P when the temporal graph is defined on a
single timestamp, since in this case any solution of the problem has span $0$.
Furthermore, deciding whether there exists a solution of MinTimelineCover that
has span equal to $0$ can be decided in polynomial time via a reduction to
2-SAT [18].

MinTimelineCover has been considered also in the parameterized complexity
framework. The definition of span leads to a problem where the algorithmic
approaches applied to Vertex Cover cannot be easily extended for the parameter
span of the solution. Indeed, in Vertex Cover for each edge we are sure than
at least one of the endpoints must be included in the solution, thus at least
one of the vertex contributes to the cost of the solution. This leads to the
textbook FPT algorithm of branching over the endpoints of any edge. For
MinTimelineCover, a vertex with span $0$ may cover a temporal edge, as the
vertex can be active only in the timestamp where the temporal edge is defined.
This makes it more challenging to design FPT algorithms when the parameter is
the span of the solution. In this case, MinTimelineCover is known to admit a
parameterized algorithm only when the input temporal graph is defined over two
timestamps [8], with a parameterized reduction to the Almost 2-SAT problem.
However, the parameterized complexity of MinTimelineCover for parameter the
span of the solution on general instances has been left open [8, 4]. The
authors of [8] have also analyzed the parameterized complexity of the variants
of Network Untangling proposed in [18], considering other parameters in
addition to the span of the solution: the number of vertices of the temporal
graph, the length of the time domain, and the number of intervals of vertex
activity.

Our contributions. We solve the open question on the parameterized complexity
of MinTimelineCover by showing that the problem is FPT in parameter $k$, the
span of a solution, even if the number of timestamps is unbounded. Our
algorithm takes time $O^{*}(2^{5k\log k})$, where the $O^{*}$ notation hides
polynomial factors. Our algorithm is divided into two phases, each using a
different technique. First, given a temporal graph $G$, we use a variant of
iterative compression, where we start from a solution $S$ of span at most $k$
on a subgraph of $G$ induced by a subset of vertices (taken across all
timestamps), and then try to maintain such a solution after adding a new
vertex of $G$ to the graph under consideration. This requires us to reorganize
which vertices involved in $S$ should be in the solution or not, and in which
timestamps. One challenge is that since the number of such timestamps is
unbounded, there are too many ways to decide how to include or not include the
vertices that are involved in $S$. We introduce the notion of a _feasible
assignment_ , which allows us to compute how the vertices in $S$ can be
reorganized (see text for definition). There are only $2^{O(k\log k)}$ ways of
reorganizing the vertices in $S$. We try each such feasible assignments $X$,
and we must then find a temporal cover of the whole graph $G$ that “agrees”
with $X$.

This leads to the second phase of the algorithm, which decides if such an
agreement cover exists through a reduction to a variant of a problem called
Digraph Pair Cut. In this problem, we receive a directed graph and forbidden
pairs of vertices, and we must delete at most $k$ arcs so that a specified
source vertex does not reach both vertices from a forbidden pair. It is known
that the problem can be solved in time $O^{*}(2^{k})$. In this work, we need a
version where the input specifies a set of deletable and undeletable arcs,
which we call Constrained Digraph Pair Cut. The Digraph Pair Cut problem and
its variants have played an important role in devising randomized kernels
using matroids [15] and, more recently, in establishing a dichotomy in the
complexity landscape of constraint satisfaction problems [12, 14]. Here, the
problem is useful since it can model the implications of choosing or not a
vertex in a solution and, in a more challenging way, allows implementing the
notion of cost using our definition of span. We hope that the techniques
developed for this reduction can be useful for other variants of temporal
graph cover.

Overview of the algorithm. Our approach is loosely inspired by some ideas from
the FPT algorithm for two timestamps, which is a reduction to Almost 2-SAT
[8]. In the latter, one is given a set of clauses with at most two variables
and must delete a minimum number of them so that those remaining are
satisfiable. We do not use Almost 2-SAT directly, but its usage for two
timestamps may help understanding the origins of our techniques and the
relevance of our reduction to Digraph Pair Cut.

The reduction from MinTimelineCover on two timestamps to Almost 2-SAT
associates each vertex $v_{i}$ with a variable $x(v_{i})$, which is true when
one should include $v_{i}$ in a vertex cover and false otherwise; each edge
$u_{i}v_{i}$ is associated with a clause $x(u_{i})\vee x(v_{i})$ (here,
$v_{i}$ represents the occurrence of vertex $v$ at timestamp $i\in\\{1,2\\}$).
This corresponds to enforcing the inclusion of $u_{i}$ or $v_{i}$ in our
vertex cover, and we can include enough copies of this clause to make it
undeletable. Since our goal is to minimize the number of base vertices $v$
with both $v_{1}$ and $v_{2}$ in the cover, we also add a clause $\neg
x(v_{1})\vee\neg x(v_{2})$. Then there is a temporal cover of $G$ of span at
most $k$ if and only if one can delete at most $k$ clauses of the latter form
to make all remaining clauses satisfiable. Even though this reduction produces
clauses with only positive or negative clauses, MinTimelineCover does not
appear to be much simpler than Almost 2-SAT in terms of FPT algorithms, and
studying the SAT formulation seems more approachable.

For $T\geq 3$ timestamps, the clauses of the form $x(u_{i})\vee x(v_{i})$ can
still be used model the vertex cover requirements, but there seems to be no
obvious way to model the span of a cover. One would need to devise a set of
clauses of size two such that choosing an interval of $t$ vertices in a cover
corresponds to deleting $t-1$ negative clauses. Our idea is to extend current
FPT algorithms for Almost 2-SAT to accommodate our cost function. In [17], the
authors propose an iterative compression FPT algorithm that starts from a
solution that deletes $k+1$ clauses, and modifies it into a solution with $k$
clauses, if possible. The algorithm relies on several clever, but complicated
properties of the dependency graph of the clauses (in which vertices are
literals and arcs are implications implied by the clauses). This algorithm
seems difficult to adapt to our problem. To our knowledge, the only other FPT
algorithm for Almost 2-SAT is that of [15]. This is achieved through a
parameterized reduction to Digraph Pair Cut. At a high level, the idea is to
start from an initial guess of assignment for a well-chosen subset of
variables, then to construct the dependency graph of the clauses. A certain
chain of implications is enforced by our initial guess, the vertex pairs to
separate correspond to contradictory literals, and deleting arcs corresponds
to deleting clauses. It turns out that, with some work, we can skip the Almost
2-SAT formulation and reduce MinTimelineCover to (a variant of) Directed Pair
Cut directly by borrowing some ideas from this reduction. This is not
immediate though. The first challenge is that the aforementioned “well-chosen
initial guess” idea cannot be used in our context, and we must develop new
tools to enumerate a bounded number of initial guesses from a partial solution
(which we call feasible assignment). The second challenge is that our
reduction to our variant of Directed Pair Cut needs a specific gadget to
enforce our cost scheme, while remaining consistent with the idea of modeling
the dependency graph of the Sat instance corresponding to the vertex problem
at hand.

##  2 Preliminaries

For an integer $n$, we denote $[n]=\\{1,\ldots,n\\}$ and for two integers $i$,
$j$, with $i<j$, we denote $[i,j]=\\{i,i+1,\dots,j-1,j\\}$. Temporal graphs
are defined over a discrete time domain ${\mathcal{T}}$, which is a sequence
$1,2\dots,T$ of timestamps. A temporal graph is also defined over a set of
vertices, called _base vertices_ , that do not change in the time domain and
are defined in all timestamps, and are associated with _vertices_ , which are
base vertices defined in specific timestamps. We use subscripts to denote the
timestamp to which a vertex belongs to, so, for a base vertex $v$ and
$t\in[T]$, we use $v_{t}$ to denote the occurrence of $v$ in timestamp $t$. A
_temporal edge_ connects two vertices, associated with distinct base vertices,
that belong to the same timestamp.

######  Definition 2.1.

A temporal graph $G=(V_{B},E,{\mathcal{T}})$ consists of

  1. 1.

A time domain ${\mathcal{T}}=\\{1,2\ldots,T\\}$;

  2. 2.

A set $V_{B}$ of _base vertices_ ; $V_{B}$ has a corresponding set $V(G)$ of
_vertices_ , which consists of base vertices in specific timestamps, defined
as follows:

$V(G)=\\{v_{t}:v\in V_{B}\wedge t\in[T]\\}.$

  3. 3.

A set $E=E(G)$ of temporal edges, which satisfies:

$E\subseteq\\{u_{t}v_{t}:u,v\in V_{B},t\in[T]\wedge u\neq v\\}.$

For a directed (static) graph $H$, we denote by $(u,v)$ an arc from vertex $u$
to vertex $v$ (we consider only directed static graphs, not directed temporal
graphs).

Given a temporal graph $G=(V_{B},E,{\mathcal{T}})$ and a set of base vertices
$B\subseteq V_{B}$, we define the set $\tau({B})$ of all vertices of $B$
across all times:

$\tau({B})=\\{v_{t}:v\in B\wedge t\in[T]\\}.$

If $B=\\{v\\}$, we may write $\tau({v})$ instead of $\tau({\\{v\\}})$.

Given a set $W\subseteq V(G)$, we denote by $G[W]$ the subgraph induced by
vertices $W$, i.e. $V(G[W])=W$ and $E(G[W])=\\{u_{t}v_{t}\in E:u_{t},v_{t}\in
W\\}$. For a subset $W_{B}\subseteq V_{B}$ of base vertices, we denote
$G[W_{B}]=G[\tau({W_{B}})]$. We also use the notation
$G-W_{B}=G[V_{B}\setminus W_{B}]$. Observe that $G[W_{B}]$ and $G-W_{B}$ are
temporal graphs over the same time domain as $G$.

In order to define the problem we are interested in, we need to define the
_assignment_ of a set of base vertices.

######  Definition 2.2.

Consider a temporal graph $G=(V_{B},E,{\mathcal{T}})$ and a set
$W_{B}\subseteq V_{B}$ of base vertices. An _assignment of $W_{B}$_ is a
subset $X\subseteq\tau({W_{B}})$ such that if $u_{p}\in X$ and $u_{q}\in X$,
with $p,q\in[T]$, then $u_{t}\in X$, for each $t\in[T]$ with $p\leq t\leq q$.
For a base vertex $u\in W_{B}$ such that there exists $t\in[T]$ with $u_{t}\in
X$, we denote by $\delta(u,X)$, $\Delta(u,X)$, respectively, the minimum and
maximum timestamp, respectively, such that $u_{\delta(u,X)},u_{\Delta(u,X)}\in
X$. If $u_{t}$ does not exist, then $\delta(u,X)=\Delta(u,X)=0$.

If $W_{B}$ is clear from the context or not relevant, then we may say that $X$
is an assignment, without specifying $W_{B}$. Note that, given an assignment
$X$ and a set $\tau({v})$, for some $v\in V_{B}$, then
$X\cap\tau({v})=\\{v_{t}:v_{t}\in X\wedge v_{t}\in\tau({v})\\}$ contains
vertices for $v$ that belong to a contiguous interval of timestamps. Consider
a set $I\subseteq[T]$ of timestamps. An assignment $X$ _intersects_ $I$ if
there exists $v_{t}\in X$ such that $t\in I$.

Now, we give the definition of _temporal cover_.

######  Definition 2.3.

Given a temporal graph $G=(V_{B},{\mathcal{T}},E)$ a _temporal cover_ of $G$
is an assignment $X$ of $V_{B}$ such that the following properties hold:

  1. 1.

For each $v\in V_{B}$ there exists at least one $v_{t}\in X$, for some
$t\in{\mathcal{T}}$.

  2. 2.

For each $u_{t}v_{t}\in E$, with $t\in[T]$, at least one of $u_{t}$, $v_{t}$
is in $X$.

For a temporal cover $X$ of $G$, the _span_ of $v$ in $X$ is defined as:
$sp(v,X)=\Delta(v,X)-\delta(v,X).$ Note that if a temporal cover $X$ contains,
for a base vertex $v\in V_{B}$, a single vertex $v_{t}$, then $sp(v,X)=0$. The
span of $X$, denoted by $sp(X)$, is then defined as:

$sp(X)=\sum_{v\in V_{B}}sp(v,X).$

Now, we are able to define MinTimelineCover (an example is presented in Fig.
1).

######  Problem 2.4.

$($MinTimelineCover$)$
Input: A temporal graph $G=(V_{B},{\mathcal{T}},E)$.
Question: Does there exist a temporal cover of $G$ of span at most $k$?

A temporal cover $S\subseteq V(G)$ of span at most $k$ will sometimes be
called a _solution_. Our goal is to decide whether MinTimelineCover is FPT in
parameter $k$.

$v$$u$$z$$w$$v_{1}$$u_{1}$$z_{1}$$w_{1}$$v_{2}$$u_{2}$$z_{2}$$w_{2}$$v_{3}$$u_{3}$$z_{3}$$w_{3}$$v_{4}$$u_{4}$$z_{4}$$w_{4}$$v_{5}$$u_{5}$$z_{5}$$w_{5}$$v_{6}$$u_{6}$$z_{6}$$w_{6}$$t=1$$t=2$$t=3$$t=4$$t=5$$t=6$
Figure 1: An example of MinTimelineCover on a temporal graph $G$ consisting of
four base vertices and six timestamps. For each timestamp, we draw the
temporal edges of $G$, for example for $t=2$, the temporal edges are
$v_{2}u_{2}$, $v_{2}w_{2}$, $u_{2}w_{2}$, $z_{2}w_{2}$. Also note that in
$t=1$ and $t=6$ no temporal edge is defined. A temporal cover
$X=\\{v_{5},u_{2},u_{3},u_{4},z_{3},z_{4},w_{2}\\}$ is represented with grey
rectangles. Note that $\delta(v,X)=\Delta(v,X)=5$, $\delta(u,X)=2$,
$\Delta(u,X)=4$, $\delta(z,X)=3$, $\Delta(z,X)=4$,
$\delta(w,X)=\Delta(w,X)=2$. It follows that $sp(X)=3$.

##  3 An FPT Algorithm

In this section we present our FPT algorithm, which consists of two parts:

  1. 1.

The iterative compression technique.

  2. 2.

A reduction to the Constrained Digraph Pair Cut problem.

Before presenting the main steps of our algorithm, we present the main idea
and some definitions. Recall that our parameter, that is the span of a
solution of MinTimelineCover, is denoted by $k$.

Consider a temporal graph $G$ and assume we have a temporal cover $S$ of span
at most $k$ of the subgraph $G-\\{w\\}$, for some base vertex $w\in V_{B}$.
The idea of the iterative compression step is, starting from $S$, to show how
to decide in FPT time whether there exists a solution of MinTimelineCover for
$G$. This is done by solving a subproblem, called Restricted Timeline Cover,
where we must modify $S$ to consider $w$. A solution to this subproblem is
computed by branching on the assignments of base vertices having a positive
span in $S$ and on $w$, and then reducing the problem to Constrained Digraph
Pair Cut. Restricted Timeline Cover is defined as follows.

######  Problem 3.1.

$($Restricted Timeline Cover$)$
Input: A temporal graph $G=(V_{B},{\mathcal{T}},E)$, a vertex $w\in V_{B}$, a
temporal cover $S$ of $G-\\{w\\}$ of span at most $k$.
Output: Does there exist a temporal cover of $G$ of span at most $k$?

For technical reasons that will become apparent later, we will assume that the
temporal graph contains no edge at timestamps $1$ and $T$, i.e.
$G[\\{v_{1},v_{T}:v\in V_{B}\\}]$ is an edgeless graph (as in Fig. 1). It is
easy to see that if this is not already the case, we can add two such “dummy”
timestamps, where $G$ does not contain any temporal edge. Indeed, since there
are no temporal edges in these two timestamps, then $G$ has a temporal cover
of span at most $k$ if and only the same graph with dummy timestamps has a
temporal cover of span at most $k$.

Informally, if we are able to solve Restricted Timeline Cover in FPT time,
then we can obtain an FPT algorithm for MinTimelineCover as well. Indeed, we
can first compute a temporal cover on a small subset of base vertices (for
example a single vertex), and then we can add, one at a time, the other
vertices of the graph. This requires at most $|V_{B}|$ iterations, and each
time a vertex is added, we compute a solution of Restricted Timeline Cover to
check whether it is possible to find a temporal cover of span at most $k$
after the addition of a vertex.

### Iterative Compression

We now present our approach based on iterative compression to solve the
Restricted Timeline Cover problem. Given a solution $S$ for $G-\\{w\\}$, we
focus on the vertices of $V_{B}$ that have a positive span in $S$ and vertex
$w$. An example of our approach, that illustrates the sets of base vertices
and vertices used by the algorithm, is presented in Fig. 2.

Consider the input of Restricted Timeline Cover that consists of a temporal
graph $G=(V_{B},{\mathcal{T}},E)$, a vertex $w\in V_{B}$, and a temporal cover
$S$ of $G-\\{w\\}$ of span at most $k$. Define the following sets associated
with $S$:

$\displaystyle V_{S}$ $\displaystyle=\\{v\in V_{B}:\exists
p,q\in[T],p<q,\mbox{ such that $v_{p},v_{q}\in S$ }\\}\cup\\{w\\}$
$\displaystyle V^{\prime}_{S}$ $\displaystyle=\\{v_{t}:v_{t}\in S,v\in
V_{S}\setminus\\{w\\}\\}\cup\\{w_{t}:t\in[T]\\}.$

The set $V_{S}$ is defined as the set of base vertices having span greater
than $0$ in $S$, plus vertex $w$. $V^{\prime}_{S}$ contains the vertices in
$V(G)$ associated with $V_{S}$, in particular: (1) the vertices corresponding
to the base vertices in $V_{S}\setminus\\{w\\}$ that are included in $S$ and
(2) vertices corresponding to the base vertex $w$ in every timestamp.

Define the following set $I_{S}$ of timestamps associated with
$V_{S}\setminus\\{w\\}$:

$I_{S}=\\{t\leavevmode\nobreak\ \in[T]:u_{t}\in V^{\prime}_{S}\text{ for some
$u\in V_{S}\setminus\\{w\\}$ }\\}.$

Essentially, $I_{S}$ contains those timestamps where the base vertices of
$V_{S}\setminus\\{w\\}$, that is of span greater than zero, have associated
vertices in $S$. These timestamps are essential for computing a solution of
Restricted Timeline Cover, that is to compute whether there exists a temporal
cover of $G[V_{B}]$ of span at most $k$ starting from $S$. We define now the
sets of base vertices and vertices associated with $S$ and having a span equal
to $0$:

$\displaystyle Z_{S}$ $\displaystyle=V_{B}\setminus V_{S}\quad\quad
Z^{\prime}_{S}=S\setminus V^{\prime}_{S}.$

First, we show two easy properties of $S$ and $I_{S}$ on the temporal graph
$G-\\{w\\}$.

######  Lemma 3.2.

Let $S$ be a solution of MinTimelineCover on instance $G-\\{w\\}$ and let
$I_{S}$ be the associated set of timestamps. Then $|I_{S}|\leq 2k$.

######  Lemma 3.3.

Let $S$ be a solution of MinTimelineCover on instance $G-\\{w\\}$. Then,
$sp(Z^{\prime}_{S})=0$. Moreover, $Z^{\prime}_{S}$ covers each temporal edge
of $G-\\{w\\}$ not covered by $V^{\prime}_{S}\setminus\tau({w})$.

Now, we introduce the concept of feasible assignment, which is used to “guess”
how $S$ is rearranged in a solution of Restricted Timeline Cover. Recall that
an assignment $X$ intersects a set $I_{S}$ of timestamps if there exists
$v_{t}\in X$ such that $t\in I_{S}$.

######  Definition 3.4 (Feasible assignment).

Consider an instance of Restricted Timeline Cover that consists of a temporal
graph $G=(V_{B},{\mathcal{T}},E)$, a vertex $w\in V_{B}$, a temporal cover $S$
of $G-\\{w\\}$ of span at most $k$, and sets $V_{S},V^{\prime}_{S}$ and
$I_{S}$ associated with $S$. We say that an assignment
$X\subseteq\tau({V_{S}})$ of $V_{S}$ is a _feasible assignment_ (with respect
to $G,S$, and $I_{S}$) if all of the following conditions hold:

  1. 1.

the span of $X$ is at most $k$;

  2. 2.

every edge of $G[V_{S}]$ is covered by $X$;

  3. 3.

$X\cap\tau({w})$ is a non-empty assignment of $\\{w\\}$;

  4. 4.

for every $v\in V_{S}\setminus\\{w\\}$, at least one of the following holds:
(1) $X\cap\tau({v})$ is empty; (2) $X\cap\tau({v})$ is an assignment of
$\\{v\\}$ that intersects with $I_{S}$; or (3) $X\cap\tau({v})$ contains a
vertex $v_{t}$ such that $v_{t}w_{t}\in E$ and $w_{t}\notin X\cap\tau({w})$.

Given a feasible assignment $X$, we denote

$M_{S}(X)=\\{v\in V_{S}:X\cap\tau({v})\neq\emptyset\\}\quad\quad\quad
N_{S}(X)=\\{v\in V_{S}:X\cap\tau({v})=\emptyset\\}$

Informally, notice that point 4 considers the possible cases for a feasible
assignment of the vertices of a base vertex $v\in V_{S}\setminus\\{w\\}$ :
none of the associated vertices in $I_{S}$ belongs to the computed solution
(case 4.(1)), or some of its associated vertices in $I_{S}$ belongs to the
solution, case 4.(2) and case 4.(3), where the latter case is forced by the
need of covering temporal edge $v_{t}w_{t}$, with $t\in I_{s}$, not covered by
$w_{t}$.

Note that $M_{S}(X)$ and $N_{S}(X)$ form a partition of $V_{S}$. Also note
that $G,S$, and $I_{S}$ are fixed in the remainder, so we assume that all
feasible assignments are with respect to $G,S$, and $I_{S}$ without explicit
mention. We now relate feasible assignments to temporal covers.

######  Definition 3.5.

Let $X^{*}$ be a temporal cover of $G$ and let $X$ be a feasible assignment.
We say that $X^{*}$ _agrees_ with $X$ if:

  * •

for each $v\in M_{S}(X)$, $X^{*}\cap\tau({v})=X\cap\tau({v})$;

  * •

for each $v\in N_{S}(X)$ and each $t\in I_{S}$, $X^{*}$ contains every
neighbor $u_{t}$ of $v_{t}$ such that $u_{t}\in\tau({Z_{S}})$.

The intuition of $X^{*}$ agreeing with $X$ is as follows. For $v\in M_{S}(X)$,
$X$ “knows” which vertices of $\tau({v})$ should be in the solution, and we
require $X^{*}$ to contain exactly those. For $v\in N_{S}(X)$, we interpret
that $X$ does not want any vertex $v_{t}$ with $t\in I_{S}$. Thus, to cover
the edges incident to $v_{t}$ that go outside of $V_{S}$, we require $X^{*}$
to contain the other endpoint. Note an important subtlety: we act “as if”
$X^{*}$ should not contain $v_{t}$ or other vertices of $N_{S}(X)$ with
timestamp in $I_{S}$, but the definition does not forbid it. Hence, $X^{*}$
_can_ contain a vertex of $N_{S}(X)$ in some timestamps of $I_{S}$, as long as
$X^{*}$ contains also its neighbors (in $I_{S}$) outside $V_{S}$.

The main purpose of feasible assignments and agreement is as follows.

######  Lemma 3.6.

Let $X^{*}$ be a temporal cover of $G$ of span at most $k$. Then there exists
a feasible assignment $X$ such that $X^{*}$ agrees with $X$.

######  Proof 3.7.

Construct $X\subseteq X^{*}$ as follows: add $X^{*}\cap\tau({w})$ to $X$, and
for $v\in V_{S}\setminus\\{w\\}$, add $X^{*}\cap\tau({v})$ to $X$ if and only
if $X^{*}\cap\tau({v})$ intersects with the set $I_{S}$, or if it contains a
vertex $v_{t}$ incident to an edge $v_{t}w_{t}\in E$ such that $w_{t}\notin
X^{*}\cap\tau({w})$. Note that since $X^{*}$ is an assignment of $V_{B}$, $X$
is an assignment of $V_{S}$.

We first focus on arguing that $X$ satisfies each condition of a feasible
assignment (Definition 3.4). For Condition 1, since $X^{*}$ has span at most
$k$ and $X\subseteq X^{*}$, it is clear that $X$ also has span at most $k$.
For Condition 3, $X^{*}\cap\tau({w})$ is non-empty by the definition of a
temporal cover, and we added $X^{*}\cap\tau({w})$ to $X$. For Condition 4, we
explicitly require in our construction of $X$ that for each $v\in
V_{S}\setminus\\{w\\}$, if $X\cap\tau({v})$ is non-empty, then it is equal to
$X^{*}\cap\tau({v})$ and it either intersects with $I_{S}$ or covers an edge
not covered by $X\cap\tau({w})=X^{*}\cap\tau({w})$.

Let us focus on Condition 2. Let $u_{t}v_{t}\in E(G[V_{S}])$. If $u=w$, then
if we did not add $w_{t}$ to $X$, $X^{*}$ must contain $v_{t}$ and we added
$X^{*}\cap\tau({v})$ to $X$, thereby covering the edge. The same holds if
$v=w$. Assume $u\neq w,v\neq w$, and suppose without loss of generality that
$X^{*}$ contains $u_{t}$ to cover the edge. Suppose for contradiction that $X$
does not cover $u_{t}v_{t}$. Then we did not add $X^{*}\cap\tau({u})$ to $X$,
which implies that $X^{*}\cap\tau({u})$ does not intersect with $I_{S}$. In
particular, $t\notin I_{S}$. Recall that $S$, the temporal cover of
$G-\\{w\\}$, only intersects with $\tau({u})$ and $\tau({v})$ in timestamps
contained in $I_{S}$. Hence, $S$ cannot cover $u_{t}v_{t}$, a contradiction.
We deduce that $X$ covers every edge. Therefore, $X$ is a feasible assignment.

It remains to show that $X^{*}$ agrees with $X$. For $v\in M_{S}(X)$,
$X^{*}\cap\tau({v})=X\cap\tau({v})$ by the construction of $X$. For $v\in
N_{S}(X)$, there is no $v_{t}\in X^{*}$ with $t\in I_{S}$, as otherwise we
would have added $X^{*}\cap\tau({v})$ to $X$. For every such $v_{t}$, $X^{*}$
must contain all of its neighbors in $\tau({Z_{S}})$ to cover the edges, as
required by the definition of agreement.

It remains to show that the number of feasible assignments has bounded size
and can be enumerated efficiently. We first show the latter can be achieved
through the following steps. Start with $X$ as an empty set and then apply the
following steps:

  1. (1)

Branch into every non-empty assignment $X_{w}$ of $\\{w\\}$ of span at most
$k$. In each branch, add the chosen subset $X_{w}$ to $X$;

  2. (2)

For every edge $v_{t}w_{t}\in E(G[V_{S}])$ such that $w_{t}\notin X_{w}$, add
$v_{t}$ to $X$;

  3. (3)

For every $v\in V_{S}\setminus\\{w\\}$, such that $X\cap\tau({v})=\emptyset$
at this moment, branch into $|I_{S}|+1$ options: either add no vertex of
$\tau({v})$ to $X$, or choose a vertex $v_{t}$ and add it to $X$, where $t\in
I_{S}$;

  4. (4)

For every $v\in V_{S}\setminus\\{w\\}$ such that $X\cap\tau({v})\neq\emptyset$
at this moment, branch into every assignment $X_{v}$ of $\\{v\\}$ of span at
most $k$ that contains every vertex of $X\cap\tau({v})$ (if no such assignment
exists, abort the current branch). For each such branch, add every vertex of
$X_{v}\setminus X$ to $X$.

######  Theorem 3.8.

The above steps enumerate every feasible assignment in time $O(2^{4k\log
k}T^{3}n)$, where $n=|V_{B}|$.

### Reducing to Constrained Digraph Pair Cut

Our objective is now to list every feasible assignment and, for each of them,
to verify whether there is a temporal cover that agrees with it. More
specifically, consider a feasible assignment $X\subseteq\tau({V_{S}})$. Our
goal is to decide whether there is a temporal cover $X^{*}$ of span at most
$k$ that agrees with $X$. Since we branch over every possible feasible
assignment $X$, if there is a temporal cover $X^{*}$ of $G$ of span at most
$k$, then by Theorem 3.8 our enumeration will eventually consider an $X$ that
$X^{*}$ agrees with, and hence we will be able to decide of the existence of
$X^{*}$.

We show that finding $X^{*}$ reduces to the Constrained Digraph Pair Cut
problem, as we define it below. For a directed graph $H$, we denote its set of
arcs by $A(H)$ (to avoid confusion with $E(G)$, which is used for the edges of
an undirected graph $G$). For $F\subseteq A(H)$, we write $H-F$ for the
directed graph with vertex set $V(H)$ and arc set $A(H)\setminus F$.

######  Problem 3.9.

$($Constrained Digraph Pair Cut$)$
Input: A directed graph $H=(V(H),A(H))$, a source vertex $s\in V(H)$, a set of
vertex pairs $P\subseteq{{V(H)}\choose 2}$ called _forbidden pairs_ , a subset
of arcs $D\subseteq A(H)$ called _deletable arcs_ , and an integer
$k^{\prime}$.
Output: Does there exist a set of arcs $F\subseteq D$ of $H$ such that
$|F|\leq k^{\prime}$ and such that, for each $\\{u,v\\}\in P$, at least one of
$u$, $v$ is not reachable from $s$ in $H-F$?

It is known that Constrained Digraph Pair Cut can be solved in time
$O^{*}(2^{k^{\prime}})$ [15], but a few remarks are needed before proceeding.
In [15], the authors only provide an algorithm for the _vertex-deletion_
variant, and do not consider deletable/undeletable arcs. It is easy to make an
arc undeletable by adding enough parallel paths between the two endpoints, and
we show at the end of the section that our formulation of Constrained Digraph
Pair Cut reduces to the simple vertex-deletion variant. The vertex-deletion
variant also admits a randomized polynomial kernel, and other FPT results are
known for weighted arc-deletion variants [13].

So let us fix a feasible assignment $X$ for the remainder of the section. We
will denote $M_{S}=M_{S}(X)$ and $N_{S}=N_{S}(X)$. We also consider the
following set of vertices associated with $N_{S}$:

$\displaystyle N^{\prime}_{S}=\\{v_{2}:v\in N_{S}\\}\quad\quad\quad$
$\displaystyle N^{\prime\prime}_{S}=\\{v_{t}\in\tau({N_{S}}):t\in I_{S}\\}.$

For each base vertex $v\in N_{S}$, we need $N^{\prime}_{S}$ to contain any
vertex of $\tau({v})$ in time $[2,T-1]$, so we choose $v_{2}$ arbitrarily.
Then, $N^{\prime\prime}_{S}$ contains those vertices $v_{t}$, with $t\in
I_{S}$, not chosen by the feasible assignment $X$. Note that according to our
definition of agreement, a solution $X^{*}$ should contain all the neighbors
of $N^{\prime\prime}_{S}$ vertices that are in $Z_{S}$. Recall that we have
defined $Z_{S}=V_{B}\setminus V_{S}$ and $Z^{\prime}_{S}=S\setminus
V^{\prime}_{S}$. By Lemma 3.3 we know that $Z^{\prime}_{S}$ covers each
temporal edge of $G[V_{B}\setminus\\{w\\}]$ not covered by $S\cap
V^{\prime}_{S}$, and that $sp(Z^{\prime}_{S})=0$. We may assume that for each
$v\in Z_{S}$, there is exactly one $t\in[T]$ such that $v_{t}\in
Z^{\prime}_{S}$ (there cannot be more than one since $Z^{\prime}_{S}$ has span
$0$, and if there is no such $t$, we can add any $v_{t}$ without affecting the
span). Furthermore, we will assume that for each $v\in Z_{S}$, the vertex
$v_{t}$ in $Z^{\prime}_{S}$ is not $v_{1}$ nor $v_{T}$. Indeed, since we
assume that the first and last timestamps of $G$ have no edges, if
$v_{t}=v_{1}$ or $v_{t}=v_{T}$, then $v_{t}$ covers no edge and we may safely
change $v_{p}$ to another vertex of $\tau({v})$.

$v$$u$$z$$v_{2}$$u_{2}$$z_{2}$$v_{3}$$u_{3}$$z_{3}$$v_{4}$$u_{4}$$z_{4}$$v_{5}$$u_{5}$$z_{5}$$t=2$$t=3$$t=4$$t=5$$v_{2}$$u_{2}$$z_{2}$$v_{3}$$u_{3}$$z_{3}$$v_{4}$$u_{4}$$z_{4}$$v_{5}$$u_{5}$$z_{5}$$t=2$$t=3$$t=4$$t=5$
Figure 2: An example of application of iterative compression (timestamps $1$
and $6$ are not shown as they are edgeless). In the left part, we represent
solution $S=\\{v_{2},v_{3},u_{3},u_{4},z_{4}\\}$, where the vertices in $S$
are highlighted with grey rectangles. Note that $I_{S}=\\{2,3,4\\}$,
$V_{S}=\\{v,u\\}$, $V^{\prime}_{S}=\\{v_{2},v_{3},u_{3},u_{4}\\}$,
$Z_{S}=\\{z\\}$, $Z^{\prime}_{S}=\\{z_{4}\\}$. In the right part, we represent
in grey a feasible assignment $X$ associated with $S$,
$X=\\{u_{2},u_{3},u_{4}\\}$; in light grey we highlight
$N^{\prime}_{S}=\\{v_{2}\\}$. The sets associated with $S$ and $X$ are:
$M_{S}=\\{u\\}$, $N_{S}=\\{v\\}$, $N^{\prime}_{S}=\\{v_{2}\\}$,
$N^{\prime\prime}_{S}=\\{v_{2},v_{3},v_{4}\\}$. The reduction to Constrained
Digraph Pair Cut eventually leads to the solution of MinTimelineCover
represented in Fig. 1.

The following observation will be useful for our reduction to Constrained
Digraph Pair Cut.

Let $u_{t}v_{t}\in E(G)$ such that $u\in N_{S}$ and $v\notin M_{S}$. Then
$v\in Z_{S}$ and, if $u_{t}\notin N^{\prime\prime}_{S}$, we have $v_{t}\in
Z^{\prime}_{S}$.

Now, given a feasible assignment $X\subseteq V^{\prime}_{S}$, sets $M_{S}$,
$N_{S}$, $N^{\prime}_{S}$, $N^{\prime\prime}_{S}$, $Z_{S}$, and
$Z^{\prime}_{S}$, we present our reduction to the Constrained Digraph Pair Cut
problem. We construct an instance of this problem that consists of the
directed graph $H=(V(H),A(H))$, the set of forbidden (unordered) pairs
$P\subseteq{{V(H)}\choose 2}$, and the deletable arcs $D\subseteq A(H)$ by
applying the following steps. The second step in the construction is the most
important and is shown in Figure 3. The intuition of these steps is provided
afterwards.

  1. 1.

add to $H$ the source vertex $s$;

  2. 2.

for each $v\in Z_{S}\cup N_{S}$, let $v_{i}$ be the vertex of
$Z^{\prime}_{S}\cup N^{\prime}_{S}$, where $i\in[2,T-1]$. Add to $H$ the
vertices
$v^{+}_{{1}},\ldots,v^{+}_{{i-1}},v^{-}_{{i}},v^{+}_{{i+1}},\ldots,v^{+}_{{T}}$,
the vertices $b_{v,j},c_{v,j},d_{v,j}$, for $j\in[T]\setminus\\{i\\}$, and the
set of arcs shown in Figure 3, that is there are arcs $(v^{+}_{{j}},b_{v,j})$,
$(v^{+}_{{j}},c_{v,j})$, $(c_{v,j},d_{v,j})$, $(d_{v,j},v^{-}_{{j}})$, for
each $j\in[T]\setminus\\{i\\}$ and four directed paths: (1) from $b_{v,i-1}$
to $b_{v,1}$, (2) from $c_{v,1}$ to $c_{v,i-1}$, (3) from $b_{v,i+1}$ to
$b_{v,T}$ and (4) from $c_{v,T}$ to $c_{v,i+1}$.

Add to $D$ the set of deletable arcs $(c_{v,j},d_{v,j})$, for
$j\in[T]\setminus\\{i\\}$.

Then add the following pairs to $P$:

    1. (a)

$\\{d_{v,h},b_{v,j}\\}$, with $1\leq h<j\leq i-1$;

    2. (b)

$\\{d_{v,h},b_{v,j}\\}$, with $i+1\leq j<h\leq T$;

    3. (c)

$\\{c_{v,h},d_{v,j}\\}$, with $1\leq h\leq i-1\leq i+1\leq j\leq T$;

    4. (d)

$\\{c_{v,h},d_{v,j}\\}$, with $1\leq j\leq i-1\leq i+1\leq h\leq T$.

Note that we have created $T+3(T-1)=4T-3$ vertices in $H$ in this step. The
subgraph of $H$ induced by these vertices will be called the _gadget
corresponding to $v$_.

  3. 3.

for each temporal edge $u_{t}v_{t}\in E(G)$ such that
$u_{t},v_{t}\in\tau({Z_{S}})\cup(\tau({N_{S}})\setminus
N^{\prime\prime}_{S})$, there are three cases. First note that at least one of
$u_{t}$ or $v_{t}$ is in $Z^{\prime}_{S}$. Indeed, if $u,v\in Z_{S}$, this is
because an element of $Z^{\prime}_{S}$ must cover the temporal edge, and if
$u\in N_{S}$, then $v_{t}\in Z^{\prime}_{S}$ by Observation 3 (or if $v\in
N_{S},u_{t}\in Z^{\prime}_{S}$). The subcases are then:

    1. (a)

if $u_{t},v_{t}\in Z^{\prime}_{S}\cup N^{\prime}_{S}$, add the pair
$\\{u^{-}_{{t}},v^{-}_{{t}}\\}$ to $P$;

    2. (b)

if $u_{t}\in Z^{\prime}_{S}\cup N^{\prime}_{S},v_{t}\notin Z^{\prime}_{S}\cup
N^{\prime}_{S}$, add the arc $(u^{-}_{{t}},v^{+}_{{t}})$ to $H$;

    3. (c)

if $v_{t}\in Z^{\prime}_{S}\cup N^{\prime}_{S},u_{t}\notin Z^{\prime}_{S}\cup
N^{\prime}_{S}$, add the arc $(v^{-}_{{t}},u^{+}_{{t}})$ to $H$;

  4. 4.

for each temporal edge $u_{t}v_{t}\in E(G)$ such that
$u_{t}\in(\tau({M_{S}})\setminus X)\cup N^{\prime\prime}_{S}$ and
$v_{t}\in\tau({Z_{S}})$, there are two cases:

    1. (a)

if $v_{t}\notin Z^{\prime}_{S}$, add the arc $(s,v^{+}_{{t}})$ to $H$;

    2. (b)

if $v_{t}\in Z^{\prime}_{S}$, add the pair $\\{s,v^{-}_{{t}}\\}$ to $P$.

Define $k^{\prime}=k-sp(X)$. This concludes the construction. We will refer to
the elements 1, 2, 3, 4 of the above enumeration as the _Steps_ of the
construction. Note that the only deletable arcs in $D$ are the arcs
$(c_{v,j},d_{v,j})$ introduced in Step 2.

Figure 3: Gadget for $v_{i}\in Z^{\prime}_{S}\cup N^{\prime}_{S}$, where
$i\in[2,T-1]$.  We assume that there exist temporal edges $u_{t}v_{t}\in
E(G)$, where $t\in\\{i-1,i+1\\}$, such that $u_{t}\in(\tau({M_{S}})\setminus
X)\cup N^{\prime\prime}_{S}$, $v_{t}\in\tau({Z_{S}})$ and $v_{t}\notin
Z^{\prime}_{S}$, thus arcs from $s$ to $v^{+}_{{t}}$ are added. The dashed
arcs represent deletable arcs.

From here, the interpretation of $H$ is that if we delete arc set $F$, then

  1. (p1)

For $v_{t}\notin Z^{\prime}_{S}\cup N^{\prime}_{S}$ we should include $v_{t}$
in $X^{*}$ if and only if $s$ reaches $v^{+}_{{t}}$ in $H-F$;

  2. (p2)

For $v_{t}\in Z^{\prime}_{S}\cup N^{\prime}_{S}$ we should include $v_{t}$ in
$X^{*}$ if and only if $s$ does _not_ reach $v^{-}_{{t}}$ in $H-F$.

The idea behind the steps of the construction is then as follows (and is
somewhat easier to describe in the reverse order of steps). Step 4 describes
an initial set of vertices that $s$ is forced to reach, which correspond to
vertices that are forced in $X^{*}$. A vertex $v_{t}$ in $\tau({Z_{S}})$ is
forced in $X^{*}$ if it is in an edge $u_{t}v_{t}$ and $u_{t}\in\tau({M_{S}})$
but $u_{t}\notin X$. By our definition of agreement, $v_{t}$ is also forced if
$u_{t}\in N_{S}^{\prime\prime}$. Step 4 handles both situations: if
$v_{t}\notin Z^{\prime}_{S}$, we force $s$ to reach $v^{+}_{{t}}$ with the arc
$(s,v^{+}_{{t}})$, which is not deletable. If $v_{t}\in Z^{\prime}_{S}$, then
$v^{-}_{{t}}\in V(H)$, and $s$ is forced to _not_ reach $v^{-}_{{t}}$ by
adding $\\{s,v^{-}_{{t}}\\}$ to $P$. By (p1) and (p2), both cases correspond
to including $v_{t}$ in $X^{*}$. Then, Step 3 ensures that each temporal edge
is “covered”: for a temporal edge $u_{t}v_{t}$, a pair of the form
$\\{u^{-}_{{t}},v^{-}_{{t}}\\}$ in $P$ requires that $s$ does not reach one of
the two, i.e. that we include one in $X^{*}$, and an undeletable arc of the
form $(u^{-}_{{t}},v^{+}_{{t}})$ enforces that if $s$ reaches $u^{-}_{{t}}$
(i.e. $u_{t}\notin X^{*}$), then $s$ reaches $v^{+}_{{t}}$ (i.e. $v_{t}\in
X^{*}$). The reason why $Z^{\prime}_{S}$ is needed in our construction is that
each edge has at least one negative corresponding vertex, so that no other
case needs to be considered in Step 3.

Finally, Step 2 enforces the number of deleted arcs to correspond to the span
of a solution. That is, it ensures that if we want to add to $X^{*}$ a set of
$h$ vertices of base vertex $v\in Z_{S}$ to our solution of Restricted
Timeline Cover (so with a span equal to $h-1$), then we have to delete $h-1$
deletable arcs of the corresponding gadget of $H$ in order to obtain a
solution to Constrained Digraph Pair Cut (and vice-versa). Indeed, consider
the gadget in Fig. 3. If $v_{i}$ is not included in $X^{*}$, then in the
gadget $s$ reaches $h$ positive vertices $v_{l}^{+},\dots,v_{r}^{+}$ (and
$v^{-}_{{i}}$).  It follows that vertices $b_{v,l},\dots,b_{v,r}$,
$c_{v,l},\dots,c_{v,r}$ and $d_{v,l},\dots,d_{v,r}$ are all reachable from
$s$. The pairs $\\{d_{v,x},b_{v,y}\\}$ defined at Step 2, where either $l\leq
x\leq y\leq r-1$ if $r<i$, or $l+1\leq x\leq y\leq r$ if $l>i$, ensures that
arcs $(c_{v,j},d_{v,j})$, with $j\in[l,r-1]$ in the former case or with
$j\in[l+1,r]$ in the latter case, are deleted.

If $v_{i}$ is included in $X^{*}$, then in the gadget $s$ reaches $h-1$
positive vertices $v_{l}^{+},\dots,v_{r}^{+}$, with $i\in[l,r]$, and must not
reach negative vertex $v^{-}_{{i}}$. It follows that vertices
$b_{v,l},\dots,b_{v,r}$, $c_{v,l},\dots,c_{v,r}$ and $d_{v,l},\dots,d_{v,r}$
are all reachable from $s$. Then $h-1$ arcs $(c_{v,j},d_{v,j})$, with
$j\in[l,r]\setminus\\{i\\},$ must be deleted, due to the pairs
$\\{d_{v,x},b_{v,y}\\}$, $\\{c_{v,x},d_{v,y}\\}$ defined at Step 2.

Note that Step 2 is the reason we added dummy timestamps $1$ and $T$. If
$v_{1}$ or $v_{T}$ were allowed to be in $Z^{\prime}_{S}\cup N^{\prime}_{S}$,
we would need a different gadget for these cases as they behave a bit
differently, along with more cases in the proofs. Adding the edgeless
timestamps lets us bypass these cases. We now proceed with the details.

######  Lemma 3.10.

There exists a solution of Restricted Timeline Cover that agrees with $X$ if
and only if there is $F\subseteq D$ with $|F|\leq k^{\prime}$ such that $s$
does not reach a forbidden pair in $H-F$. Moreover, given such a set $F$, a
solution of Restricted Timeline Cover can be computed in polynomial time.

######  Proof 3.11 (Sketch of the proof).

($\Rightarrow$) Suppose that there exists a solution $X^{*}$ of Restricted
Timeline Cover that agrees with $X$. By definition of Restricted Timeline
Cover, $X^{*}$ has span at most $k$. Note that for $v\in M_{S}$, the agreement
requires that $X^{*}\cap\tau({v})=X\cap\tau({v})$, and so the span of $v$ in
$X^{*}$ is the same as the span of $v$ in $X$. Thus

$\sum_{v\in Z_{S}\cup N_{S}}sp(v,X^{*})\leq k-sp(X)=k^{\prime}.$

We may assume that for every $v\in V_{B}$, at least one of
$v_{2},\dots,v_{T-1}$ is in $X^{*}$, as otherwise we add one arbitrarily
without affecting the span (if only $v_{1}$ or $v_{T}$ is in $X^{*}$, remove
it first). For each $v\in Z_{S}\cup N_{S}$, consider the gadget corresponding
to $v$ in $H$ and delete some of its dashed arcs as follows (we recommend
referring to Figure 3).

First, if only one of $\tau({v})$ is in $X^{*}$, no action is required on the
gadget. So assume that $X^{*}\cap\tau({v})$ has at least two vertices; in the
following we denote $v_{l}=v_{\delta(v,X^{*})}$ and
$v_{r}=v_{\Delta(v,X^{*})}$ the vertices associated with $v$ having minimum
and maximum timestamp, respectively, contained in $X^{*}$. We assume that
$l,r\in[2,T-1]$ and $l<r$. Note that
$X^{*}\cap\tau({v})=\\{v_{l},v_{l+1},\dots,v_{r}\\}$.

Let $v_{i}\in Z^{\prime}_{S}\cup N^{\prime}_{S}$, where $i\in[2,T-1]$. Then

  * •

suppose that $l,r\in[2,i-1]$, then: delete every arc $(c_{v,q},d_{v,q})$, with
$l\leq q\leq r-1$

  * •

suppose that with $l,r\in[i+1,T-1]$, then: delete every arc
$(c_{v,q},d_{v,q})$, with $l+1\leq q\leq r$

  * •

suppose that $l\in[2,i]$ and $r\in[i,T-1]$, then: delete every arc
$(c_{v,q},d_{v,q})$, with $l\leq q\leq i-1$, and delete every arc
$(c_{v,q},d_{v,q})$, with $i+1\leq q\leq r$.

We see that by construction for all $v\in Z_{S}\cup N_{S}$, the number of arcs
deleted in the gadget corresponding to $v$ is equal to the number of vertices
in $X^{*}\cap\tau({v})$ minus one, that is the span of $v$ in $X^{*}$. Since
these vertices have span at most $k^{\prime}$, it follows that we deleted at
most $k^{\prime}$ arcs from $H$. Denote by $H^{\prime}$ the graph obtained
after deleting the aforementioned arcs. We argue that in $H^{\prime}$, $s$
does not reach a forbidden pair. To this end, we claim the following.

######  Claim 1.

For $v\in Z_{S}\cup N_{S}$ and $t\in[T]$, if $s$ reaches $v^{+}_{{t}}$ in
$H^{\prime}$, then $v_{t}\in X^{*}$, and if $s$ reaches $v^{-}_{{t}}$ in
$H^{\prime}$, then $v_{t}\notin X^{*}$.

Now, armed with the above claim, we can prove that in $H^{\prime}$, $s$ does
not reach both vertices of a forbidden pair $q\in P$, thus concluding this
direction of the proof.

($\Leftarrow$) Suppose that there is a set $F\subseteq D$ with at most
$k^{\prime}$ arcs such that $s$ does not reach a forbidden pair in $H-F$.
Denote $H^{\prime}=H-F$. We construct $X^{*}$ from $F$, which will also show
that it can be reconstructed from $F$ in polynomial time. Define
$X^{*}\subseteq V(G)$ as follows:

  * •

for each $v\in M_{S}$, add every element of $X\cap\tau({M_{S}})$ to $X^{*}$;

  * •

for each $v_{t}\in V(G)\setminus\tau({M_{S}})$, we add $v_{t}$ to $X^{*}$ if
and only if one of the following holds: (1) $v^{+}_{{t}}\in V(H)$ and $s$
reaches $v^{+}_{{t}}$ in $H^{\prime}$; or (2) $v^{-}_{{t}}\in V(H)$, and $s$
does _not_ reach $v^{-}_{{t}}$ in $H^{\prime}$;

  * •

for each $v_{j},v_{h}\in X^{*}$ with $j<h$, add $v_{t}$ to $X^{*}$ for each
$t\in[j+1,h-1]$.

Note that $X^{*}$ agrees with $X$. Indeed, for $v\in M_{S}$, there is no
gadget corresponding to $v$ in the construction and thus we only add
$X\cap\tau({v})$ to $X^{*}$. For $u\in N_{S}$, consider $u_{t}\in
N_{S}^{\prime\prime}$ and a neighbor $v_{t}$ of $u_{t}$ in $\tau({Z_{S}})$. If
$v_{t}\notin Z^{\prime}_{S}$, Step 4 adds an undeletable arc from $s$ to
$v^{+}_{{t}}$, hence $s$ reaches that vertex and we put $v_{t}$ in $X^{*}$. If
$v_{t}\in Z^{\prime}_{S}$, Step 4 adds $\\{s,v^{-}_{{t}}\\}$ to $P$, and thus
$s$ does not reach $v^{-}_{{t}}$ in $H^{\prime}$, and again we add $v_{t}$ to
$X^{*}$. Therefore, we add all the $\tau({Z_{S}})$ neighbors of $u_{t}$ to
$X^{*}$, and so it agrees with $X$. We can prove that $X^{*}$ covers every
temporal edge of $G$ and that $sp(X^{*})\leq k$.

### Wrapping up

Before concluding, we must show that we are able to use the results of [15] to
get an FPT algorithm for Constrained Digraph Pair Cut, as we have presented
it. As we mentioned, the FPT algorithm in [15] studied the vertex-deletion
variant and does not consider undeletable elements, but this is mostly a
technicality. Roughly speaking, in our variant, it suffices to replace each
vertex with enough copies of the same vertex, and replace each deletable arc
$(u,v)$ with a new vertex, adding arcs from the $u$ copies to that vertex, and
arcs from that vertex to the $v$ copies. Deleting $(u,v)$ corresponds to
deleting that new vertex. For undeletable arcs, we apply the same process but
repeat it $k^{\prime}+1$ times.

######  Lemma 3.12.

The Constrained Digraph Pair Cut problem can be solved in time $O^{*}(2^{k})$,
where $k$ is the number of arcs to delete.

We are able now to prove the main result of our contribution.

######  Theorem 3.13.

MinTimelineCover on a temporal graph $G=(V_{B},E,{\mathcal{T}})$ can be solved
in time $O^{*}(2^{5k\log k})$.

######  Proof 3.14.

First, we discuss the correctness of the algorithm we presented. Assume that
we have an ordering on the base vertices of $G$ and that $v$ is the first
vertex of this ordering. A solution $S$ of MinTimelineCover on $G[\\{v\\}]$ is
equal to $S=\emptyset$.

Then for $i$, with $i\in[2,|V_{B}|]$, let $G_{i}$ be the temporal graph
induced by the first $i$ vertices and let $w$ be the $i+1$-th vertex. Given a
solution $S$ of MinTimelineCover on instance $G_{i}$ of span at most $k$, we
can decide whether there exists a solution of MinTimelineCover on instance
$G_{i+1}$ by computing whether there exists a solution $X^{*}$ of the
Restricted Timeline Cover problem on instance $G_{i}$, $w$, $S$. By Lemma 3.6
and by Theorem 3.8 if there exists such an $X^{*}$, then there exists a
feasible assignment $X$ that agrees with $X^{*}$. By Lemma 3.10 we can
compute, via the reduction to Constrained Digraph Pair Cut, whether there
exists a solution of Restricted Timeline Cover on instance on instance
$G_{i}$, $w$, $S$, and if so obtain such a solution (if no such solution
$X^{*}$ exists, then Lemma 3.10 also says that we will never return a
solution, since every feasible assignment $X$ that we enumerate will lead to a
negative instance of Constrained Digraph Pair Cut). Thus the Restricted
Timeline Cover subproblem is solved correctly, and once it is solved on
$G_{|V_{B}|}$, we have a solution to MinTimelineCover.

Now, we discuss the complexity of the algorithm. We must solve Restricted
Timeline Cover $|V_{B}|$ times. For each iteration, by Theorem 3.8 we can
enumerate the feasible assignments in $O(2^{4k\log k}T^{3}n)$ time. For each
such assignment, the reduction from Restricted Timeline Cover to Constrained
Digraph Pair Cut requires polynomial time, and each generated instance can be
solved in time $O^{*}(2^{k})$. The time dependency on $k$ is thus
$O^{*}(2^{4k\log k}\cdot 2^{k})$, which we simplify to $O^{*}(2^{5k\log k})$.

##  4 Conclusion

We have presented a randomized FPT algorithm for the MinTimelineCover problem,
a variant of Vertex Cover on temporal graph recently considered for timeline
activities summarizations. We point out some relevant future directions on
this topic: (1) to improve, if possible, the time complexity of
MinTimelineCover by obtaining a single exponential time algorithm (of the form
$O^{*}(c^{k})$); (2) to establish whether MinTimelineCover admits a polynomial
kernel, possibly randomized (which it might, since Constrained Digraph Pair
Cut famously admits a randomized polynomial kernel); and (3) to extend the
approach to other variants of Network Untangling.

## References

  * [1] Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis, and Christoforos L. Raptopoulos.  The temporal explorer who returns to the base.  J. Comput. Syst. Sci., 120:179–193, 2021.  doi:10.1016/j.jcss.2021.04.001.
  * [2] Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis, and Viktor Zamaraev.  Temporal vertex cover with a sliding time window.  J. Comput. Syst. Sci., 107:108–123, 2020.  doi:10.1016/j.jcss.2019.08.002.
  * [3] Benjamin Merlin Bumpus and Kitty Meeks.  Edge exploration of temporal graphs.  In Paola Flocchini and Lucia Moura, editors, Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5-7, 2021, Proceedings, volume 12757 of Lecture Notes in Computer Science, pages 107–121. Springer, 2021.  doi:10.1007/978-3-030-79987-8\\_8.
  * [4] Riccardo Dondi.  Insights into the complexity of disentangling temporal graphs.  In Ugo Dal Lago and Daniele Gorla, editors, Proceedings of the 23rd Italian Conference on Theoretical Computer Science, ICTCS 2022, Rome, Italy, September 7-9, 2022, volume 3284 of CEUR Workshop Proceedings, pages 1–13. CEUR-WS.org, 2022.
  * [5] Riccardo Dondi and Mohammad Mehdi Hosseinzadeh.  Finding colorful paths in temporal graphs.  In Rosa María Benito, Chantal Cherifi, Hocine Cherifi, Esteban Moro, Luis M. Rocha, and Marta Sales-Pardo, editors, Complex Networks & Their Applications X - Volume 1, Proceedings of the Tenth International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2021, Madrid, Spain, November 30 - December 2, 2021, volume 1015 of Studies in Computational Intelligence, pages 553–565. Springer, 2021\.  doi:10.1007/978-3-030-93409-5\\_46.
  * [6] Thomas Erlebach, Michael Hoffmann, and Frank Kammer.  On temporal graph exploration.  J. Comput. Syst. Sci., 119:1–18, 2021.  doi:10.1016/j.jcss.2021.01.005.
  * [7] Till Fluschnik, Hendrik Molter, Rolf Niedermeier, Malte Renken, and Philipp Zschoche.  Temporal graph classes: A view through temporal separators.  Theor. Comput. Sci., 806:197–218, 2020.  doi:10.1016/j.tcs.2019.03.031.
  * [8] Vincent Froese, Pascal Kunz, and Philipp Zschoche.  Disentangling the computational complexity of network untangling.  In Luc De Raedt, editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, pages 2037–2043. ijcai.org, 2022.  doi:10.24963/ijcai.2022/283.
  * [9] Thekla Hamm, Nina Klobas, George B. Mertzios, and Paul G. Spirakis.  The complexity of temporal vertex cover in small-degree graphs.  In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 - March 1, 2022, pages 10193–10201. AAAI Press, 2022.
  * [10] Petter Holme.  Modern temporal network theory: a colloquium.  The European Physical Journal B, 88(9):234, 2015.
  * [11] David Kempe, Jon M. Kleinberg, and Amit Kumar.  Connectivity and inference problems for temporal networks.  J. Comput. Syst. Sci., 64(4):820–842, 2002.  doi:10.1006/jcss.2002.1829.
  * [12] Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström.  Directed flow-augmentation.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 938–947, 2022.
  * [13] Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström.  Directed flow-augmentation.  In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 \- 24, 2022, pages 938–947. ACM, 2022.  doi:10.1145/3519935.3520018.
  * [14] Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström.  Flow-augmentation iii: Complexity dichotomy for boolean csps parameterized by the number of unsatisfied constraints.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3218–3228. SIAM, 2023.
  * [15] Stefan Kratsch and Magnus Wahlström.  Representative sets and irrelevant vertices: New tools for kernelization.  J. ACM, 67(3):16:1–16:50, 2020.  doi:10.1145/3390887.
  * [16] Andrea Marino and Ana Silva.  Königsberg sightseeing: Eulerian walks in temporal graphs.  In Paola Flocchini and Lucia Moura, editors, Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5-7, 2021, Proceedings, volume 12757 of Lecture Notes in Computer Science, pages 485–500. Springer, 2021.  doi:10.1007/978-3-030-79987-8\\_34.
  * [17] Igor Razgon and Barry O’Sullivan.  Almost 2-sat is fixed-parameter tractable.  J. Comput. Syst. Sci., 75(8):435–450, 2009.  doi:10.1016/j.jcss.2009.04.002.
  * [18] Polina Rozenshtein, Nikolaj Tatti, and Aristides Gionis.  The network-untangling problem: from interactions to activity timelines.  Data Min. Knowl. Discov., 35(1):213–247, 2021.  doi:10.1007/s10618-020-00717-5.
  * [19] Huanhuan Wu, James Cheng, Silu Huang, Yiping Ke, Yi Lu, and Yanyan Xu.  Path problems in temporal graphs.  Proc. VLDB Endow., 7(9):721–732, 2014.  doi:10.14778/2732939.2732945.
  * [20] Huanhuan Wu, James Cheng, Yiping Ke, Silu Huang, Yuzhen Huang, and Hejun Wu.  Efficient algorithms for temporal path computation.  IEEE Trans. Knowl. Data Eng., 28(11):2927–2942, 2016.  doi:10.1109/TKDE.2016.2594065.
  * [21] Philipp Zschoche, Till Fluschnik, Hendrik Molter, and Rolf Niedermeier.  The complexity of finding small separators in temporal graphs.  J. Comput. Syst. Sci., 107:72–92, 2020.  doi:10.1016/j.jcss.2019.07.006.

## Appendix

### Proof of Lemma 3.2

######  Lemma 4.1.

Let $S$ be a solution of MinTimelineCover on instance
$G[V_{B}\setminus\\{w\\}]$ and let $I_{S}$ be the associated set of
timestamps. Then $|I_{S}|\leq 2k$.

######  Proof 4.2.

The result follows from the fact that, since $|V_{S}\setminus\\{w\\}|\leq k$
and $V_{S}\setminus\\{w\\}$ contains only vertices of positive span, $2k$
timestamps contribute at least $k$ to the span of $S$.

### Proof of Lemma 3.3

######  Lemma 4.3.

Let $S$ be a solution of MinTimelineCover on instance $G-\\{w\\}$. Then,
$sp(Z^{\prime}_{S})=0$. Moreover, $Z^{\prime}_{S}$ covers each temporal edge
of $G-\\{w\\}$ not covered by $V^{\prime}_{S}\setminus\tau({w})$.

######  Proof 4.4.

Since $S$ is a cover of $G-\\{w\\}$, it follows that the temporal edges not
covered by $V^{\prime}_{S}\setminus\\{w\\}$ must be covered by vertices of
$Z^{\prime}_{S}$. Furthermore, by the definition of $Z^{\prime}_{S}$, it
follows that $sp(Z^{\prime}_{S})=0$.

#### Proof of Theorem 3.8

######  Theorem 4.9.

The above steps enumerate every feasible assignment in time $O(2^{4k\log
k}T^{3}n)$, where $n=|V_{B}|$.

######  Proof 4.10.

We first argue that every feasible assignment is enumerated. Consider a
feasible assignment $X$. First, consider the (non-empty) intersection
$X_{w}=X\cap\tau({w})$. Since in Step (1) we branch into every non-empty
assignment of $\\{w\\}$, then we eventually enumerate $X_{w}$. In what
follows, we assume that we are in the branch where $X_{w}$ is added.

Now, consider a vertex $v\in V_{S}\setminus\\{w\\}$ and let
$X_{v}=X\cap\tau({v})$. If no vertex of $\tau({v})$ belongs to $X$ (hence
$X_{v}$ is empty), then Step (3) enumerates this case (note that Step (2) does
not add a vertex of $\tau({v})$ either: $X_{v}$ empty implies that there is no
edge of the form $v_{t}w_{t}$ with $w_{t}\notin X$, since $X$ must cover this
edge). Assume that $X_{v}$ is non-empty. By the definition of a feasible
assignment, some $v_{t}$ is in $X_{v}$ to cover an edge incident to a vertex
of $\tau({w})$ not covered by $X_{w}$, or $v_{t}$ is in a timestamp of
$I_{S}$. In the former case, $v_{t}$ is added in Step (2), and in the latter
case, one of the branches of Step (3) will add $v_{t}$ to the set under
construction. Since the span of $X$ and hence of $X_{v}$ is at most $k$, it
follows that $X_{v}$ is an assignment of $\\{v\\}$ of span at most $k$, and
Step (4) will branch into a case where it adds $X\cap\tau({v})$. It follows
that $X$ will be enumerated at some point.

Now, we discuss the number of feasible assignments enumerated by Steps (1) –
(4). Step (1) is computed in $O(T^{2})$ time, as there are $O(T^{2})$ possible
non-empty intervals $X_{w}$. For each branch defined at Step (1), Step (2) can
be computed in $Tn$ time as the vertices in $w$ can have at most $Tn$
neighbors.

Step (3), for each vertex $v\in V_{S}\setminus\\{w\\}$, branches into at most
$2k+1$ cases, as from Lemma 3.2 we have that $|I_{S}|\leq 2k$. Since there are
at most $k$ vertices in $V_{S}\setminus\\{w\\}$, the number of branches
explored in Step (3) is at most $(2k+1)^{k}$.

As for Step (4), for each branch defined in Step (3) for $v\in
V_{S}\setminus\\{w\\}$ such that $X\cap\tau({v})\neq\emptyset$, it branches
over $O(k^{2})$ possible choices of timestamps $a$, $b$ that are endpoints of
$X_{v}$. Again since $|V_{S}|\leq k$, the number of branches explored in Step
(4) is at most $O(k^{2k})$.

Thus the overall time to enumerate the feasible assignments with Steps (1) –
(4) is $O(T^{2}\cdot Tn\cdot(2k+1)^{k}k^{2k})$, which is $O(2^{4k\log
k}T^{3}n)$ for $k\geq 3$ (and if $k\leq 2$, it is constant and this still
holds).

### Proof of Observation 3

Let $u_{t}v_{t}\in E(G)$ such that $u\in N_{S}$ and $v\notin M_{S}$. Then
$v\in Z_{S}$ and, if $u_{t}\notin N^{\prime\prime}_{S}$, we have $v_{t}\in
Z^{\prime}_{S}$.

######  Proof 4.11.

There cannot be an edge $u_{t}v_{t}$ between two vertices of $\tau({N_{S}})$,
since $X$ must cover every edge in $G[V_{S}]$ and contains no vertices of
$\tau({N_{S}})$. Thus $v\notin N_{S}$, and since $v\notin M_{S}$, we have
$v\in Z_{S}$. Next suppose that $u_{t}\notin N^{\prime\prime}_{S}$. Then
$t\notin I_{S}$, implying that $u_{t}\notin S$. Hence, the edge must be
covered by $v_{t}$, which is in $S\setminus V^{\prime}_{S}=Z^{\prime}_{S}$.

### Proof of Lemma 3.10

######  Lemma 4.12.

There exists a solution of Restricted Timeline Cover that agrees with $X$ if
and only if there is $F\subseteq D$ with $|F|\leq k^{\prime}$ such that $s$
does not reach a forbidden pair in $H-F$. Moreover, given such a set $F$, a
solution of Restricted Timeline Cover can be computed in polynomial time.

######  Proof 4.13.

($\Rightarrow$) Suppose that there exists a solution $X^{*}$ of Restricted
Timeline Cover that agrees with $X$. By definition of Restricted Timeline
Cover $X^{*}$ has span at most $k$. Note that for $v\in M_{S}$, agreement
requires that $X^{*}\cap\tau({v})=X\cap\tau({v})$, and so the span of $v$ in
$X^{*}$ is the same as the span of $v$ in $X$. Thus

$\sum_{v\in Z_{S}\cup N_{S}}sp(v,X^{*})\leq k-sp(X)=k^{\prime}.$

We may assume that for every $v\in V_{B}$, at least one of
$v_{2},\dots,v_{T-1}$ is in $X^{*}$, as otherwise we add one arbitrarily
without affecting the span (if only $v_{1}$ or $v_{T}$ is in $X^{*}$, remove
it first). For each $v\in Z_{S}\cup N_{S}$, consider the gadget corresponding
to $v$ in $H$ and delete some of its dashed arcs as follows (we recommend
referring to Figure 3).

First, if only one of $\tau({v})$ is in $X^{*}$, no action is required on the
gadget. So assume that $X^{*}\cap\tau({v})$ has at least two vertices; in the
following we denote $v_{l}=v_{\delta(v,X^{*})}$ and
$v_{r}=v_{\Delta(v,X^{*})}$ the vertices associated with $v$ having minimum
and maximum timestamp, respectively, contained in $X^{*}$. We assume that
$l,r\in[2,T-1]$ and $l<r$. Note that
$X^{*}\cap\tau({v})=\\{v_{l},v_{l+1},\dots,v_{r}\\}$.

Let $v_{i}\in Z^{\prime}_{S}\cup N^{\prime}_{S}$, where $i\in[2,T-1]$. Then

  * •

suppose that $l,r\in[2,i-1]$, then: delete every arc $(c_{v,q},d_{v,q})$, with
$l\leq q\leq r-1$

  * •

suppose that with $l,r\in[i+1,T-1]$, then: delete every arc
$(c_{v,q},d_{v,q})$, with $l+1\leq q\leq r$

  * •

suppose that $l\in[2,i]$ and $r\in[i,T-1]$, then: delete every arc
$(c_{v,q},d_{v,q})$, with $l\leq q\leq i-1$, and delete every arc
$(c_{v,q},d_{v,q})$, with $i+1\leq q\leq r$.

We see that by construction for all $v\in Z_{S}\cup N_{S}$, the number of arcs
deleted in the gadget corresponding to $v$ is equal to the number of vertices
in $X^{*}\cap\tau({v})$ minus one, that is the span of $v$ in $X^{*}$. Since
these vertices have span at most $k^{\prime}$, it follows that we deleted at
most $k^{\prime}$ arcs from $H$. Denote by $H^{\prime}$ the graph obtained
after deleting the aforementioned arcs. We argue that in $H^{\prime}$, $s$
does not reach a forbidden pair. To this end, we claim the following.

######  Claim 2.

For $v\in Z_{S}\cup N_{S}$ and $t\in[T]$, if $s$ reaches $v^{+}_{{t}}$ in
$H^{\prime}$, then $v_{t}\in X^{*}$, and if $s$ reaches $v^{-}_{{t}}$ in
$H^{\prime}$, then $v_{t}\notin X^{*}$.

######  Proof 4.14.

The proof is by induction on the distance between $s$ and the vertex. As a
base case, consider the out-neighbors of $s$ in $H^{\prime}$. Suppose that
$v^{+}_{{t}}$ is such that $(s,v^{+}_{{t}})\in A(H^{\prime})$. This arc was
added to $H$ by Step 4 because $G$ contains a temporal edge $u_{t}v_{t}$ with
$u_{t}\in(\tau({M_{S}})\setminus X)\cup N^{\prime\prime}_{S}$ and
$v_{t}\in\tau({Z_{S}})$. If $u_{t}\in\tau({M_{S}})\setminus X$, then
$u_{t}\notin X$ and $u_{t}\notin X^{*}$ either, since it agrees with $X$. Thus
we must have $v_{t}\in X^{*}$ to cover the edge. If $u_{t}\in
N^{\prime\prime}_{S}$, then $v_{t}\in X^{*}$ holds by the definition of
agreement. By inspecting the construction of $H$, we see that $s$ does not
have an out-neighbor of the form $v^{-}_{{t}}$, and so this suffices for the
base case.

Now consider a vertex of the form $v^{+}_{{t}}$ or $v^{-}_{{t}}$ at distance
greater than $1$ from $s$ in $H^{\prime}$, and assume by induction that the
claim holds for vertices of this form at a smaller distance. Suppose that this
vertex is $v^{+}_{{t}}$. By inspecting the construction, we see that the only
possible in-neighbors of $v^{+}_{{t}}$ are either $s$, or some $u^{-}_{{t}}$.
The $s$ case was handled as a base case, and so we assume the latter. Thus any
shortest path from $s$ to $v^{+}_{{t}}$ ends with an arc
$(u^{-}_{{t}},v^{+}_{{t}})$. Since $s$ reaches $u^{-}_{{t}}$ with a shorter
path, we know by induction that $u_{t}\notin X^{*}$. Moreover, the arc
$(u^{-}_{{t}},v^{+}_{{t}})$ must have been created on Step 3, and so
$u_{t}v_{t}\in E(G)$. Therefore, $v_{t}\in X^{*}$ must hold to cover
$u_{t}v_{t}$, as desired.

So consider instead a vertex of the form $v^{-}_{{t}}$ that $s$ reaches in
$H^{\prime}$. Assume for contradiction that $v_{t}\in X^{*}$. By inspecting
the construction, we see that the only in-neighbors of $v^{-}_{{t}}$ belong to
the gadget corresponding to $v$. Moreover, the only way to reach $v^{-}_{{t}}$
from $s$ is to go through some $v^{+}_{{j}}$, where $j\in[T]\setminus\\{t\\}$,
and then through some other vertices of the gadget. Consider a shortest path
from $s$ to $v^{-}_{{t}}$ in $H^{\prime}$, and let $v^{+}_{{j}}$ be the first
vertex of the gadget corresponding to $v$ in this path. By induction, we may
assume that $v_{j}\in X^{*}$, and hence the span of $v$ is at least one, since
we are currently assuming that $v_{t}\in X^{*}$.

Now, the existence of $v^{-}_{{t}}$ implies that $v_{t}\in Z^{\prime}_{S}\cup
N^{\prime}_{S}$. Consider $\\{v_{l},v_{l+1},\dots,v_{r}\\}\subseteq X^{*}$.
Then we have $l\in[2,t]$, $r\in[t,T-1]$, and $j\in[l,r]\setminus\\{t\\}$. In
this case, all the arcs $(c_{v,y},d_{v,y})$, with $y\in[l,r]\setminus\\{t\\}$
are removed. Moreover, by inspecting the steps of the construction, we see
that the only out-neighbors of $v^{+}_{{j}}$ are $b_{v,j}$ and $c_{v,j}$. Thus
$v^{+}_{{j}}$ can only reach $v^{-}_{{t}}$ through a $c_{v,y}$ and then a
$d_{v,y}$ vertex. However, because of our deletions, $v_{j}^{+}$ cannot reach
any vertex $d_{v,y}$, thus it cannot reach $v^{-}_{{t}}$, leading to a
contradiction. We deduce that $v_{t}\notin X^{*}$, which concludes the proof
of the claim.

Now, armed with the above claim, assume for contradiction that in
$H^{\prime}$, $s$ reaches both vertices of a forbidden pair $q\in P$. If $q$
was created on Step 3, then $q=\\{u^{-}_{{t}},v^{-}_{{t}}\\}$, where
$u_{t}v_{t}$ is an edge of $G$. By Claim 2, this implies that
$u_{t},v_{t}\notin X^{*}$, a contradiction since $X^{*}$ would not cover the
edge. If $q$ was created on Step 4, then $q=\\{s,v^{-}_{{t}}\\}$, where there
is an edge $u_{t}v_{t}\in E(G)$ such that $u_{t}\in(\tau({M_{S}})\setminus
X)\cup N^{\prime\prime}_{S}$ and $v_{t}\in\tau({Z_{S}})$. Under the assumption
that $s$ reaches $v^{-}_{{t}}$, Claim 2 implies that $v_{t}\notin X^{*}$. If
$u_{t}\in N^{\prime\prime}_{S}$, this contradicts the fact that $X^{*}$ agrees
with $X$, since $v_{t}$ should be in $X^{*}$. If
$u_{t}\in\tau({M_{S}})\setminus X$, then $u_{t}\notin X$ implies that
$u_{t}\notin X^{*}$ , reaching a contradiction since the edge $u_{t}v_{t}$ is
not covered.

We may thus assume that $q$ was created on Step 2. Let $v\in Z_{S}\cup N_{S}$
be the base vertex for which the corresponding gadget contains the two
vertices of $q$.

Let $v_{i}\in Z^{\prime}_{S}\cup N^{\prime}_{S}$, where $i\in[2,T-1]$. Assume
that $q$ is $\\{d_{v,h},b_{v,j}\\}$ with $h<j<i$. Then $s$ must reach
$v^{+}_{{l}}$, $c_{v,l}$, $c_{v,h}$ (possibly identical to $c_{v,l}$) and
$d_{v,h}$, with $l\leq h$. On the other hand, since $s$ reaches $b_{v,j}$, we
have that $s$ must reach $v^{+}_{{r}}$ and $b_{v,r}$, where $r\in[j,i-1]$. By
Claim 2, $v_{l},v_{r}\in X^{*}$, in which case we deleted the deletable arc
$(c_{v,h},d_{v,h})$ (since $h<j$, and either the first or third situation
arises in our list of three cases of arc deletions). Thus $s$ cannot reach
$d_{v,h}$.

Likewise, assume that $q$ is $\\{d_{v,h},b_{v,j}\\}$ with $i<j<h$. Then $s$
must reach $c_{v,r}$, $c_{v,h}$ (possibly identical to $c_{v,r}$) and
$d_{v,h}$, with $r\geq h$. On the other hand, $s$ must reach $v^{+}_{{l}}$,
with $l\leq j<h$. By Claim 2, $v_{l},v_{r}\in X^{*}$, in which case we deleted
the deletable arc $(c_{v,h},d_{v,h})$. Thus $s$ cannot reach $d_{v,h}$.

Assume that $q$ is $\\{c_{v,h},d_{v,j}\\}$ or $\\{c_{v,j},d_{v,h}\\}$ with
$h<i<j$. Then $s$ must reach $v^{+}_{{l}}$, $c_{v,l}$, $c_{v,h}$, possibly
identical to $c_{v,l}$ and $d_{v,h}$, if $(c_{v,h},d_{v,h})$ is not deleted.
On the other hand, $s$ must reach $c_{v,r}$, $c_{v,j}$, possibly identical to
$c_{v,r}$, and $d_{v,j}$, if $(c_{v,i},d_{v,j})$ is not deleted. By Claim 2,
$v_{l},v_{r}\in X^{*}$, in which case we deleted the deletable arcs
$(c_{v,h},d_{v,h})$ and $(c_{v,j},d_{v,j})$. Thus $s$ cannot reach $d_{v,h}$
and $d_{v,j}$.

Having handled every forbidden pair, we deduce that we can remove at most
$k^{\prime}$ edges from $H$ so that $s$ does not reach any of them.

($\Leftarrow$) Suppose that there is a set $F\subseteq D$ with at most
$k^{\prime}$ arcs such that $s$ does not reach a forbidden pair in $H-F$.
Denote $H^{\prime}=H-F$. We construct $X^{*}$ from $F$, which will also show
that it can be reconstructed from $F$ in polynomial time. Define
$X^{*}\subseteq V(G)$ as follows:

  * •

for each $v\in M_{S}$, add every element of $X\cap\tau({M_{S}})$ to $X^{*}$;

  * •

for each $v_{t}\in V(G)\setminus\tau({M_{S}})$, we add $v_{t}$ to $X^{*}$ if
and only if one of the following holds: (1) $v^{+}_{{t}}\in V(H)$ and $s$
reaches $v^{+}_{{t}}$ in $H^{\prime}$; or (2) $v^{-}_{{t}}\in V(H)$, and $s$
does _not_ reach $v^{-}_{{t}}$ in $H^{\prime}$;

  * •

for each $v_{j},v_{h}\in X^{*}$ with $j<h$, add $v_{t}$ to $X^{*}$ for each
$t\in[j+1,h-1]$.

Note that $X^{*}$ agrees with $X$. Indeed, for $v\in M_{S}$, there is no
gadget corresponding to $v$ in the construction and thus we only add
$X\cap\tau({v})$ to $X^{*}$. For $u\in N_{S}$, consider $u_{t}\in
N_{S}^{\prime\prime}$ and a neighbor $v_{t}$ of $u_{t}$ in $\tau({Z_{S}})$. If
$v_{t}\notin Z^{\prime}_{S}$, Step 4 adds an undeletable arc from $s$ to
$v^{+}_{{t}}$, hence $s$ reaches that vertex and we put $v_{t}$ in $X^{*}$. If
$v_{t}\in Z^{\prime}_{S}$, Step 4 adds $\\{s,v^{-}_{{t}}\\}$ to $P$, and thus
$s$ does not reach $v^{-}_{{t}}$ in $H^{\prime}$, and again we add $v_{t}$ to
$X^{*}$. Therefore, we add all the $\tau({Z_{S}})$ neighbors of $u_{t}$ to
$X^{*}$, and so it agrees with $X$.

We claim that $X^{*}$ covers every temporal edge of $G$. Since $X$ is a
feasible assignment, every temporal edge $u_{t}v_{t}\in E(G)$ with $u,v\in
V_{S}$ is covered by $X$, and thus also by $X^{*}$ since $X\subseteq X^{*}$.

Next consider a temporal edge $u_{t}v_{t}\in E(G)$ with
$u_{t}\in\tau({M_{S}})\cup N^{\prime\prime}_{S}$ and $v_{t}\in\tau({Z_{S}})$.
If $u_{t}\in X$, the temporal edge is covered since $X\subseteq X^{*}$. So
assume that $u_{t}\notin X$, i.e. $u_{t}\in(\tau({M_{S}})\setminus X)\cup
N^{\prime\prime}_{S}$. If $v_{t}\notin Z^{\prime}_{S}$, Step 4 adds an
undeletable arc from $s$ to $v^{+}_{{t}}$, which implies that this arc is in
$H^{\prime}$. Thus $s$ reaches $v^{+}_{{t}}$ and $v_{t}\in X^{*}$ by
construction, and $u_{t}v_{t}$ is covered. If $v_{t}\in Z^{\prime}_{S}$, then
$\\{s,v^{-}_{{t}}\\}$ is in $P$ owing to Step 4, and thus $s$ does not reach
$v^{-}_{{t}}$ in $H^{\prime}$. Again by construction, $v_{t}\in X^{*}$.

Finally, consider a temporal edge $u_{t}v_{t}\in E(G)$ with
$u_{t},v_{t}\in\tau({Z_{S}})\cup(\tau({N_{S}})\setminus
N^{\prime\prime}_{S}$). As argued in Step 3, we know that at least one of
$u_{t}$ or $v_{t}$ is in $Z^{\prime}_{S}$. Suppose that both $u_{t},v_{t}\in
Z^{\prime}_{S}\cup N^{\prime}_{S}$. Then by Step 3,
$\\{u^{-}_{{t}},v^{-}_{{t}}\\}\in P$, and there is at least one of the two
that $s$ does not reach. By construction, one of $u_{t}$ or $v_{t}$ is in
$X^{*}$ and the temporal edge is covered. So suppose, without loss of
generality, that $u_{t}\in Z^{\prime}_{S}\cup N^{\prime}_{S},v_{t}\notin
Z^{\prime}_{S}\cup N^{\prime}_{S}$. Then $u^{-}_{{t}}\in V(H)$ and
$v^{+}_{{t}}\in V(H)$. If $s$ does not reach $u^{-}_{{t}}$ in $H^{\prime}$,
then $u_{t}\in X^{*}$ and the temporal edge is covered. Thus we may assume
that $s$ reaches $u^{-}_{{t}}$ in $H^{\prime}$. By Step 3, there is an
undeletable arc $(u^{-}_{{t}},v^{+}_{{t}})$ in $H$, and thus in $H^{\prime}$,
which implies that $s$ reaches $v^{+}_{{t}}$. Thus $v_{t}\in X^{*}$ and the
temporal edge is covered. Note that we have covered every case of a possible
temporal edge, and we deduce that $X^{*}$ covers every temporal edge.

We next claim that $sp(X^{*})\leq k$. Since $X^{*}\cap\tau({M_{S}})=X$, the
vertices in $M_{S}$ have span equal to $sp(X)$. We must argue that the
vertices of $V_{B}\setminus M_{S}$ have a span of at most
$k^{\prime}=k-sp(X)$. Consider a vertex $v\in V_{B}\setminus M_{S}=N_{S}\cup
Z_{S}$ that has span $sp(v,X^{*})$ more than $0$ in $X^{*}$ (recall that
$sp(v,X^{*})$ denotes the span of $v$ in $X^{*}$). We want to show that
$sp(v,X^{*})$ edges of $H$ were deleted in the gadget corresponding to $v$.

In the following we denote by $v_{l}$ and $v_{r}$, with $l,r\in[2,T-1]$ the
minimum and maximum timestamp, respectively, such that $v_{l}\in X^{*}$ and
$v_{r}\in X^{*}$.

Let $v_{i}\in Z^{\prime}_{S}\cup N^{\prime}_{S}$, where $i\in[l,r]$. Suppose
that $r<i$. Then by the construction of $X^{*}$, $s$ reaches $v^{+}_{{l}}$ and
$v^{+}_{{r}}$, hence $s$ reaches (1) $c_{v,l}$ and thus $c_{v,j}$, for each
$j\in[l,i-1]$, and (2) $b_{v,r}$ and thus $b_{v,j}$, for each $j\in[1,r]$.
Thus the arcs $(c_{v,j},d_{v,j})$, with $j\in[l,r-1]$, have to be deleted due
the forbidden pairs $\\{d_{v,j},b_{v,y}\\}$, with $l\leq j<y\leq r$. This
amounts to $r-l$ deletions, which is the span of $v$ in $X^{*}$.

Suppose instead that with $i<l$. Similarly to the previous case, by the
construction, $s$ reaches $v^{+}_{{l}}$ and $v^{+}_{{r}}$, hence $s$ reaches
(1) $c_{v,r}$ and thus $c_{v,j}$, for each $j\in[i+1,r]$, and (2) $b_{v,l}$
and thus $b_{v,j}$, for each $j$ with $j\in[l,T]$. Thus the arcs
$(c_{v,j},d_{v,j})$, for each $j\in[l+1,r]$, have to be deleted due the
forbidden pairs $\\{d_{v,j},b_{v,y}\\}$, with $l\leq y<j\leq r$. Again, this
amounts to $r-l$ deletions, which is the span of $v$ in $X^{*}$.

Finally, suppose that $l\leq i\leq r$. We have three cases depending on the
fact that $l=i$, $r=i$ or $l<i<r$. Consider the first case $l=i<r$. Thus by
the construction of $X^{*}$, $s$ reaches $v_{r}^{+}$ but does not reach
$v_{i}^{-}$. Moreover, $s$ reaches $c_{v,r}$ thus $s$ reaches $c_{v,j}$, for
each $j\in[i+1,r]$. Thus arcs $(c_{v,j},d_{v,j})$, for each $j\in[i+1,r]$,
have to be deleted in order to make $v^{-}_{{i}}$ not reachable from $s$. This
amounts to $r-i=r-l$ deletions, which is the span of $v$ in $X^{*}$.

Consider the second case $l<i=r$. Similarly to the previous case, $s$ reaches
$v^{+}_{{l}}$ but does not reach $v^{-}_{{i}}$. Moreover, $s$ reaches
$c_{v,j}$, for each $j$ with $j\in[l,i-1]$. Thus arcs $(c_{v,j},d_{v,j})$, for
each $j\in[l,i-1]$ have to be deleted in order to make $v^{-}_{{i}}$ not
reachable from $s$. This amounts to $i-j=r-l$ deletions, which is the span of
$v$ in $X^{*}$.

Finally, consider the third case $l<i<r$. Then arcs $(c_{v,j},d_{v,j})$, with
$j\in[l,i-1]$ and $(c_{v,j},d_{v,j})$, with $j\in[i+1,r]$, have to be deleted
due to forbidden pairs $\\{c_{v,j},d_{v,z}\\}$, with $j<i<z$ and forbidden
pairs $\\{c_{v,z},d_{v,j}\\}$, with $z<i<j$. This requires $i-l+r-i=r-l$
deletions, which is the span of $v$ in $X^{*}$.

We thus see that each vertex $v$ of $V_{B}\setminus M_{S}$ has a span that is
at most the number of arcs deleted in the gadget of $H$ corresponding to $v$.
Therefore, $X^{*}$ is a temporal cover of span at most $sp(X)+k^{\prime}\leq
k$, thus completing the proof.

### Proof of Lemma 3.12

######  Lemma 4.15.

The Constrained Digraph Pair Cut problem can be solved in time $O^{*}(2^{k})$,
where $k$ is the number of arcs to delete.

######  Proof 4.16.

We call Vertex-Deletion Digraph Pair Cut the problem in which, given a
directed graph $H$, a source $s\in V(H)$, pairs $P\subseteq{V\choose 2}$, and
integer $k$, we must decide whether there is $R\subseteq V(H)\setminus\\{s\\}$
with $|R|\leq k$ such that in $H-R$, $s$ does not reach both $u$ and $v$ for
every $\\{u,v\\}\in P$ (note that $H-R$ removes vertices here, not arcs). In
[15, Theorem 6.1], this problem was shown to be solvable in time
$O^{*}(2^{k})$. We show that Constrained Digraph Pair Cut as we defined it
reduces to Vertex-Deletion Digraph Pair Cut, with the same parameter value
$k$.

Suppose that we have an instance of Digraph Pair Cut, with directed graph $H$,
source $s$, pairs $P$, deletable arcs $D$, and integer $k$. From this
instance, obtain an instance of Vertex-Deletion Digraph Pair Cut with directed
graph $H^{\prime}$, source $s^{\prime}$, pairs $P^{\prime}$, and integer $k$
as follows (note that $k$ is unchanged). First for each $u\in V(H)$, add $k+1$
copies $u^{1},\ldots,u^{k+1}$ of $u$ to $V(H^{\prime})$. Also add a new vertex
$s^{\prime}$ to $V(H^{\prime})$, which serves as the source for the modified
instance. Add to $A(H^{\prime})$ the set of arcs
$(s^{\prime},s^{1}),\ldots,(s^{\prime},s^{k+1})$. Then for each deletable arc
$(u,v)\in D$, add to $H^{\prime}$ a new vertex $q_{{u},{v},{1}}$, and the set
of arcs

$\\{(u^{i},q_{{u},{v},{1}}):i\in[k+1]\\}\cup\\{(q_{{u},{v},{1}},v^{j}:j\in[k+1]\\}$

Finally, for each undeletable arc $(u,v)\in A(H)\setminus D$, add to
$H^{\prime}$ the $k+1$ new vertices
$q_{{u},{v},{1}},q_{{u},{v},{2}},\ldots,q_{{u},{v},{k+1}}$, and then add to
$A(H^{\prime})$ the set of arcs

$\\{(u^{i},q_{{u},{v},{l}}):i\in[k+1],l\in[k+1]\\}\cup\\{(q_{{u},{v},{l}},v^{j}):l\in[k+1],j\in[k+1]\\}$

In other words, each vertex of $H$ has $k+1$ corresponding vertices in
$H^{\prime}$, making the latter pointless to delete. For $(u,v)\in D$,
deleting the arc corresponds to deleting $q_{{u},{v},{1}}$ since it removes
the path of length $2$ from every $u^{i}$ to every $v^{j}$. For $(u,v)\in
A(H)\setminus D$, there are too many $q_{{u},{v},{l}}$ copies, making them
pointless to delete.

Finally, for each $\\{u,v\\}\in P$, we add to $P^{\prime}$ all the pairs
$\\{u^{i},v^{j}\\}$ for every $i,j\in[k+1]$.

Assume that there is $F\subseteq D$ with $|F|\leq k$ such that $s$ reaches no
pair of $P$ in $H-F$. In $H^{\prime}$, we delete the set of vertices
$R=\\{q_{{u},{v},{1}}:(u,v)\in F\\}$. Note that $|R|=|F|\leq k$. Suppose for
contradiction that in $H^{\prime}-R$, $s^{\prime}$ reaches both
$\\{u^{i},v^{j}\\}\in P^{\prime}$. Since every arc of $H^{\prime}$ is incident
to a vertex of the form $q_{{u},{v},{l}}$, in $H^{\prime}$, the path from
$s^{\prime}$ to $u^{i}$ in $H^{\prime}-R$ has the form

$s^{\prime}\rightarrow s^{b_{0}}\rightarrow q_{{s},{x_{1}},{a_{1}}}\rightarrow
x_{1}^{b_{1}}\rightarrow q_{{x_{1}},{x_{2}},{a_{2}}}\rightarrow
x_{2}^{b_{2}}\rightarrow
q_{{x_{2}},{x_{3}},{a_{3}}}\rightarrow\ldots\rightarrow
q_{{x_{l}},{u},{a_{l+1}}}\rightarrow u^{i}$

for some vertices $x_{1},\ldots,x_{l}\in V(H)$ and indices
$b_{0},a_{1},b_{1},\ldots,a_{l+1}$. By our construction of $R$, this means
that in $H-F$, all the arcs $(s,x_{1}),(x_{1},x_{2}),\ldots,(x_{l},u)$ are
present, and that $s$ reaches $u$ in $H-F$. By the same logic, $s$ also
reaches $v$ in $H-F$, a contradiction since $\\{u^{i},v^{j}\\}\in P^{\prime}$
implies that $\\{u,v\\}\in P$. Thus $R$ is a solution for $H^{\prime}$.

Conversely, assume that there is $R\subseteq
V(H^{\prime})\setminus\\{s^{\prime}\\}$ with $|R|\leq k$ such that $s$ reaches
no pair of $P^{\prime}$ in $H^{\prime}-R$. We may assume that $R$ does not
contain a vertex $u^{i}$ with $u\in V(H)$, since $R$ cannot contain every copy
of $u$. Likewise, for undeletable $(u,v)\in A(H)\setminus D$, we may assume
that $R$ does not contain a vertex $q_{{u},{v},{l}}$ since $R$ cannot contain
every copy. Therefore, we may assume that $R$ only contains vertices of the
form $q_{{u},{v},{1}}$, where $(u,v)\in D$. Define
$F=\\{(u,v):q_{{u},{v},{1}}\in R\\}$. Note that $F$ has at most $|R|\leq k$
arcs, and they are all deletable. Now suppose for contradiction that $s$
reaches both $u,v$ for $\\{u,v\\}\in P$ in $H-F$. Hence in $H-F$ there are
paths $P_{u},P_{v}$ from $s$ to $u$ and $v$, respectively. Note that for every
arc $(x,y)$ of $P_{u}$, the vertex $q_{{x},{y},{1}}$ is still present in
$H^{\prime}-R$. Thus by replacing every $(x,y)$ with the subpath
$x^{1},q_{{x},{y},{1}},y^{1}$, we can obtain a path form $s^{\prime}$ to
$u^{1}$ in $H^{\prime}-R$. Likewise, there is a path from $s^{\prime}$ to
$v^{1}$ in $H^{\prime}-R$. This is a contradiction since $\\{u,v\\}\in P$
implies that $\\{u^{i},v^{j}\\}\in P^{\prime}$. Hence $F$ is a valid solution
for $H$.

To conclude, constructing $H^{\prime}$ can clearly be done in time polynomial
in $|V(H)|+|A(H)|$. It follows that we can solve the instance $H$ in time
$O^{*}(2^{k})$ by constructing $H^{\prime}$ and solving the vertex-deletion
variant on it.