Department of Computer Science, University of Geneva,
Switzerlandarnaud.casteigts@unige.chhttps://orcid.org/0000-0002-7819-7013
supported by French ANR, project ANR-22-CE48-0001 (TEMPOGRAL). Friedrich
Schiller University Jena, Institute of Computer Science,
Germanynils.morawietz@uni-jena.dehttps://orcid.org/0000-0002-7283-4982 LaBRI,
CNRS, Université de Bordeaux, Bordeaux INP, France and https://www.wolfp.net/
<EMAIL_ADDRESS>https://orcid.org/0000-0003-3097-3906 supported by French ANR,
project ANR-22-CE48-0001 (TEMPOGRAL). Arnaud Casteigts, Nils Morawietz, and
Petra Wolf [500]Theory of computation Graph algorithms analysis
[500]Mathematics of computing Discrete mathematics

# Distance to Transitivity: New Parameters for Taming Reachability in Temporal
Graphs

Arnaud Casteigts  Nils Morawietz  Petra Wolf

###### Abstract

A temporal graph is a graph whose edges only appear at certain points in time.
Reachability in these graphs is defined in terms of paths that traverse the
edges in chronological order (temporal paths). This form of reachability is
neither symmetric nor transitive, the latter having important consequences on
the computational complexity of even basic questions, such as computing
temporal connected components. In this paper, we introduce several parameters
that capture how far a temporal graph $\mathcal{G}$ is from being transitive,
namely, _vertex-deletion distance to transitivity_ and _arc-modification
distance to transitivity_ , both being applied to the reachability graph of
$\mathcal{G}$. We illustrate the impact of these parameters on the temporal
connected component problem, obtaining several tractability results in terms
of fixed-parameter tractability and polynomial kernels. Significantly, these
results are obtained without restrictions of the underlying graph, the
snapshots, or the lifetime of the input graph. As such, our results isolate
the impact of non-transitivity and confirm the key role that it plays in the
hardness of temporal graph problems.

###### keywords:

Temporal graphs, Parameterized complexity, Reachability, Transitivity.

###### category:

##  1 Introduction

Temporal graphs have gained attention lately as appropriate tools to capture
time-dependent phenomena in fields as various as transportation, social
networks analysis, biology, robotics, scheduling, and distributed computing.
On the theoretical side, these graphs generate interest mostly for their
intriguing features. Indeed, many basic questions are still open, with a
general feeling that existing techniques from graph theory typically fail on
temporal graphs. In fact, most of the natural questions considered in static
graphs turn out to be intractable when formulated in a temporal version, and
likewise, most of the temporal analogs of classical structural properties are
false.

One of the earliest examples is that the natural analog of Menger’s theorem
does not hold in temporal graphs [21]. Another early result is that deciding
if a temporal connected component (set of vertices that can reach each other
through temporal paths) of a certain size exists is NP-complete [6]. A more
recent and striking result is that there exist temporally connected graphs on
$\Theta(n^{2})$ edges in which every edge is critical for connectivity; in
other words, no temporal analog of sparse spanners exist unconditionally [5]
(though they do, probabilistically [11]). Moreover, minimizing the size of
such spanners is APX-hard [2, 5]. Further hardness results for problems whose
static versions are generally tractable include separators [19], connectivity
mitigation [16], exploration [17, 4], flows [1], Eulerian paths [7], and even
spanning trees [9].

Faced by these difficulties, the algorithmic community has focused on special
cases, and tools from parameterized complexity were employed with moderate
success. A natural approach here is to apply the range of classical graph
parameters to restrict either the underlying graph of the temporal graph (i.e.
which edges can exist at all) or its snapshots (i.e. which edges may exist
simultaneously). For example, finding temporal paths with bounded waiting time
at each node (which is NP-hard in general) turns out to be FPT when
parameterized by treedepth or vertex cover number of the underlying graph. But
the problem is already W[1]-hard for pathwidth (let alone treewidth) [10]. In
fact, as observed in [18], most temporal graphs problems remain hard even when
the underlying graph has bounded treewidth (sometimes, even a tree or a star
[16, 3, 4]).

A possible explanation for these results is that temporal graph problems are
_very_ hard. Another one is that parameters based on static graph properties
are not adequate. Some parameters whose definition is based on that of a
temporal graph include timed feedback vertex sets (counting the cumulative
distance to trees over all snapshots) [10] and the $p(\mathcal{G})$ parameter
from [4], that measures in a certain way how dynamic the temporal graph is and
enables polynomial kernels for the exploration problem. While these parameters
represent some progress towards finer-grained restrictions, they remain
somewhat structural in the sense that their definition is stable under re-
shuffling of the snapshots.

A key aspect of temporal graphs is that the _ordering of events_ matters.
Arguably, a truly temporal parameter should be sensitive to that. An
interesting step in this direction was recently made by Bumpus and Meeks [7],
introducing interval-membership-width, a parameter that quantifies the extent
to which the set of intervals defined by the first and last appearance of an
edge at each vertex can overlap (with application to Eulerian paths). In a
sense, this parameter measures how complex the interleaving of events could
be. Another, perhaps even more fundamental feature of temporal graphs is that
the reachability relation based on temporal paths is not guaranteed to be
symmetric or transitive. While the former is a well-known limitation of
directed graphs, the latter is specific to temporal graphs (directed or not),
and it has been suspected to be one of the main sources of intractability
since the onset of the theory. (Note that a temporal graph of bounded
interval-membership-width may still be arbitrarily non-transitive.) In the
present work, we explore new parameters that control how transitive a temporal
graph is, thereby isolating, and confirming, the role that this aspect plays
in the tractability of temporal reachability problems.

#### Our Contributions.

We introduce and investigate two parameters that measure how far a temporal
graph is from having transitive reachability. For a temporal graph
$\mathcal{G}$, our parameters directly address the reachability features of
$\mathcal{G}$, and as such, they are formulated in terms of its reachability
graph $G_{R}=(V,\\{(u,v):u\leadsto v\\})$, a directed graph whose arcs
represent the existence of temporal paths in $\mathcal{G}$, whether
$\mathcal{G}$ itself is directed or undirected. Indeed, the reachability of
$\mathcal{G}$ is transitive if and only if the arc relation of $G_{R}$ is
transitive. Two natural ways of measuring this distance are in terms of
_vertex deletion_ and _arc modification_ , namely:

  * •

_Vertex-deletion distance to transitivity_ ($\delta_{\mathrm{vd}}$) is the
minimum number of vertices whose deletion from $G_{R}$ makes the resulting
graph transitive.

  * •

_Arc-modification distance to transitivity_ ($\delta_{\mathrm{am}}$) is the
minimum number of arcs whose addition or deletion from $G_{R}$ makes the
resulting graph transitive.

Observe that vertex addition does not appear to make particular sense. As for
the arc-modification distance, we may occasionally consider its restriction to
arc-addition only ($\delta_{\mathrm{aa}}$).

Among the many problems that were shown intractable in temporal graphs, one of
the first, and perhaps most iconic one, is the computation of temporal
connected components [6] (see also [13, 23]). In order to benchmark our new
parameters, we investigate their impact on the computational complexity of
this problem. Informally, given a temporal graph $\mathcal{G}$ (defined later)
on a set of vertices $V$, a temporal connected component is a subset
$V^{\prime}\subseteq V$ such that for all $u$ and $v$ in $V^{\prime}$, $u$ can
reach $v$ by a temporal path (shorthand, $u\leadsto v$). Interestingly, the
non-transitive nature of reachability here makes it possible for such vertices
to reach each other through temporal paths that travel outside the component,
without absorbing the intermediate vertices into the component. This gives
rise to two distinct notions of components: _open_ temporal connected
components (Open-TCC) and _closed_ temporal connected components (Closed-TCC),
the latter requiring that only internal vertices are used in the temporal
paths, and both being NP-hard to compute.

The statement of our results requires a few more facts. Both algorithmic and
structural results in temporal graphs are highly sensitive to subtle
definitional variations, called _settings_. In the _non-strict_ setting, the
labels along a temporal path are only required to be non-decreasing, whereas
in the _strict_ setting, they must be increasing. It turns out that both
settings are sometimes incomparable in difficulty, and the techniques
developed for each may be different. Some temporal graphs, called _proper_ ,
have the property that no two adjacent edges share a common time label, making
it possible to ignore the distinction between strict and non-strict temporal
paths. Whenever possible, hardness results should preferably be obtained for
proper temporal graphs, so that they apply in both settings at once. Finally,
with a few exceptions, our results hold for both directed and undirected
temporal graphs.

Bearing these notions in mind, our results are the following. For Open-TCC, we
obtain an FPT algorithm with parameter $\delta_{\mathrm{vd}}$, running in time
$3^{\delta_{\mathrm{vd}}}\cdot n^{\mathcal{O}(1)}$ (in all the settings).
Unfortunately, $\delta_{\mathrm{vd}}$ turns out to be too small for obtaining
a polynomial size kernel. In fact, we show that under reasonable computational
complexity assumptions, no polynomial kernel in
$\delta_{\mathrm{vd}}+\mathrm{vc}+k$ exists (except possibly for the non-
strict undirected setting), where $k$ denotes the size of the sought tcc and
where $\mathrm{vc}$ denotes the vertex cover number of the underlying graph.
Next, we obtain an FPT algorithm running in time
$4^{\delta_{\mathrm{am}}}\cdot n^{\mathcal{O}(1)}$ for the mostly larger
parameter $\delta_{\mathrm{am}}$, and show that Open-TCC admits a polynomial
kernel of size $|M|^{3}$, where $M$ is a given arc set for which
$(V,A(G_{R})\Delta M)$ is transitive. It also admits a polynomial kernel of
size $\delta_{\mathrm{aa}}^{2}$ when restricting modification to addition-only
(again, all these results hold in all the settings). Closed-TCC, in
comparison, seems to be a harder problem, at least with respect to our
parameters. In particular, we show that it remains NP-hard even if
$\delta_{\mathrm{am}}=\delta_{\mathrm{vd}}=1$ in all the settings (through
proper graphs). It is also W[1]-hard when parameterized by
$\delta_{\mathrm{vd}}+\delta_{\mathrm{am}}+k$ in all the settings, except
possibly in the non-strict undirected setting. In fact, these two results hold
even for temporal graphs whose reachability graph misses a single arc towards
being a bidirectional clique.

Put together, these results establish clearly that non-transitivity is a
genuine source of hardness for Open-TCC. The case of Closed-TCC is less clear.
On the one hand, the parameters do not suffice to make this particular version
of the problem tractable. This is not so surprising, as the reachability graph
itself does not encode which paths are responsible for reachability, in
particular, whether these paths are internal or external in a component. On
the other hand, this gives us a separation between both versions of the
problem and provides some support for the fact that Closed-TCC may be harder
than Open-TCC, which was not known before. Finally, the negative results for
Closed-TCC can serve as a landmark result for guiding future efforts in
defining transitivity parameters that exploit more sophisticated structures
than the reachability graph.

#### Organization of the Work.

The main definitions are given in Section 2. Then, we investigate each
parameter in a dedicated section ($\delta_{\mathrm{vd}}$ in Section 3 and
$\delta_{\mathrm{am}}$ in Section 4). The limitations of these parameters in
the case of Closed-TCC are presented in Section 5. Finally, Section 6
concludes the paper with some remarks and open questions.

##  2 Preliminaries

For concepts of parameterized complexity, like FPT, W[1]-hardness, and
polynomial kernels, we refer to the standard monographs [15, 14]. A reduction
$g$ between two parameterized problems is called a _polynomial parameter
transformation_ , if the reduction can be computed in polynomial time and, if
for every input instance $(I,k)$, we have that
$(I^{\prime},k^{\prime})=g(I,k)$ with $k^{\prime}\in k^{\mathcal{O}(1)}$. We
call a polynomial time reduction from a problem $P$ to $P$ itself a _self-
reduction_.

Notation. Let $n$ be a positive integer, we denote with $[n]$ the set
$\\{1,2,\dots,n\\}$. For a decision problem $P$, we say that two instances
$I_{1},I_{2}$ of $P$ are  _equivalent_ if $I_{1}$ is a yes-instance of $P$ if
and only if $I_{2}$ is a yes-instance of $P$. For two sets $A$ and $B$, we
denote with $A\Delta B$ the symmetric difference of $A$ and $B$.

Graphs. We consider a graph $G=(V,E)$ to be a static graph. If not indicated
otherwise, we assume $G$ to be undirected. Given a (directed) graph $G$, we
denote by $V(G)$ the set of vertices of $G$, by $E(G)$ (respectively, $A(G)$)
the set of edges (arcs) of $G$. Let $G=(V,E)$ be a graph a let $X\subseteq
V(G)$ be a set of vertices. We denote by $E_{G}(X)=\\{\\{u,v\\}\in E\mid u\in
X,v\in X\\}$ the edges in $G$ between the vertices of $S$. Moreover, we define
the following operations on $G$: $G[X]=(X,E_{G}[X])$, $G-X=G[V\setminus X]$.
We call a sequence $\rho=v_{0},v_{1},\ldots,v_{r}$ of vertices a _path_ in
graph $G$ if $v_{0},\ldots,v_{r}\in V(G)$ and for $i\in[r]$,
$\\{v_{i-1},v_{i}\\}\in E(G)$. We denote with $N_{G}[v]$ the closed
neighborhood of the vertex $v\in V(G)$. A vertex set $S\subseteq V$ is a
_clique_ in an undirected graph, if each pair of vertices in $S$ is adjacent
in $G$. For a directed graph $G=(V,A)$, we call a set $S\subseteq V$ a
_bidirectional clique_ , if for every pair of distinct vertices $u,v$ in $S$,
we have $(u,v)\in A$ and $(v,u)\in A$. Let $G=(V,A)$ be a directed graph. A
_strongly connected component (scc)_ in $G$ is an inclusion maximal vertex set
$S\subseteq V$ under the property that there is a directed path in $G$ between
any two vertices of $S$. For each directed graph $G$, there is a unique
partition of the vertex set of $G$ into sccs. Moreover, this partition can be
computed in polynomial time [24].

Temporal graphs. A _temporal graph_ $\mathcal{G}$ over a set of vertices $V$
is a sequence $\mathcal{G}=(G_{1},G_{2},\dots,G_{L})$ of graphs such that for
all $t\in[L],V(G_{t})=V$. We call $L$ the _lifetime_ of $\mathcal{G}$ and for
$t\in[L]$, we call $G_{t}=(V,E_{t})$ the _snapshot graph_ of $\mathcal{G}$ at
_time step_ $t$. We might refer to $G_{t}$ as $\mathcal{G}(t)$. We call
$G=(V,E)$ with $E=\bigcup_{t\in[L]}E_{t}$ the _underlying graph_ of
$\mathcal{G}$. We denote by $V(\mathcal{G})$ the set of vertices of
$\mathcal{G}$. We write $V$ if the graph or temporal graph is clear from
context. We call an undirected temporal graph
$\mathcal{G}=(G_{1},G_{2},\dots,G_{L})$ _proper_ , if for each vertex $v\in
V(\mathcal{G})$ the degree of $v$ in $G_{t}$ is one, for each $t\leq L$. We
call a directed temporal graph $\mathcal{G}=(G_{1},G_{2},\dots,G_{L})$
_proper_ , if for each vertex $v\in V(\mathcal{G})$ either the out-degree or
the in-degree of $v$ in $G_{t}$ is zero, for each $t\leq L$. We further call a
(directed) temporal graph $\mathcal{G}$ _simple_ , if each edge (arc) exists
in exactly one snapshot. We call a sequence of vertices
$v_{0},v_{1},\ldots,v_{r}$ that form a path in the underlying graph $G$ of
$\mathcal{G}$ a _strict (non-strict) temporal path_ in $\mathcal{G}$ if for
each $i\in[r]$, there exists an $j_{i}\in[L]$ such that
$\\{v_{i-1},v_{i}\\}\in E(G_{j_{i}})$ and the sequence of indices $j_{i}$ is
increasing (non-decreasing).

For a temporal graph $\mathcal{G}$, we say that a vertex $u\in V$ _strictly
(non-strictly) reaches_ a vertex $v\in V$ if there is a strict (non-strict)
temporal path from $u$ to $v$, i.e., with $v_{0}=u$ and $v_{r}=v$. We define
the _strict (non-strict) reachability relation_ $R\subseteq V\times V$ as: for
all $u,v\in V$, $(u,v)\in R$ if and only if $u$ strictly (non-strictly)
reaches $v$. We call the directed graph $G_{R}=(V,R)$ the _strict (non-strict)
reachability graph_ of $\mathcal{G}$. We say that $G_{R}$ is transitive, resp.
symmetric, if and only if $R$ is. More generally, we say that a directed graph
$G$ is _transitive_ , if its set of arcs forms a transitive relation. For a
directed graph $G=(V,A)$ we call a set of vertices $S\subseteq V$ a
_transitivity modulator_ if $G-S$ is transitive.

Let $G$ be a transitive directed graph. Then, for any $v\in V(G)$,
$G[V\setminus\\{v\\}]$ is also transitive.

Next we define our main problems of interest in this work, finding open and
closed temporal connected components.

> Open Temporal Connected Component (Open-TCC)
> Input: Temporal graph $\mathcal{G}=(G_{1},G_{2},\dots,G_{L})$ and integer
> $k$.
> Question: Does there exists an open temporal connected component of size at
> least $k$, i.e., a subset $C\subseteq V(\mathcal{G})$ with $|C|\geq k$, such
> that for each $u,v\in C$, $u$ reaches $v$, and vice versa.

We differentiate between the strict vs. non-strict and directed vs. undirected
version of Open-TCC depending on whether we consider strict vs. non-strict
reachability and directed vs. undirected temporal graphs. We define the
problem Closed Temporal Connected Component (Closed-TCC) similarly with the
additional restriction that at least one path over which $u$ reaches $v$ is
fully contained in $C$. We abbreviate a temporal connected component as tcc.

Distance to transitivity. We introduce two parameters that measure how far the
reachability graph $G_{R}=(V,A)$ of a temporal graph is from being transitive.
The first parameter, _vertex-deletion distance to transitivity_ ,
$\delta_{\mathrm{vd}}$, counts how many vertices need to be deleted from
$G_{R}$ in order to obtain a transitive reachability graph, i.e., the size of
a minimum transitivity modulator. This parameter is especially suited for
temporal graphs for which the reachability graph consists of cliques with
small overlaps. The second parameter, _arc-modification distance to
transitivity_ , $\delta_{\mathrm{am}}$, counts how many arcs need to be added
to or removed from $G_{R}$ in order to obtain a transitive reachability graph
and is especially suited for directed temporal graphs or temporal graphs for
which the reachability graph consists of cliques with large overlaps.
Formally, we define the parameters as follows.

$\displaystyle\delta_{\mathrm{vd}}$ $\displaystyle=\min_{S\subseteq
V}(|S|)\text{ for which }G_{R}^{\prime}=G_{R}-S\text{ is transitive.}$
$\displaystyle\delta_{\mathrm{am}}$ $\displaystyle=\min_{M\subseteq V\times
V}(|M|)\text{ for which }G_{R}^{\prime}=(V,A\Delta M)\text{ is transitive.}$

For $\delta_{\mathrm{am}}$, we call the set $M$ an arc-modification set. Note
that $\delta_{\mathrm{vd}}\leq 2\cdot\delta_{\mathrm{am}}$, since the
endpoints of an arc-modification set form a transitivity modulator.

###  2.1 Basic Observations

Next, we present basic observations that motivate the study of the considered
parameters.

######  Lemma 2.1 ([6]).

Let $\mathcal{G}$ be a temporal graph with reachability graph $G_{R}$. Then a
set $S\subseteq V(\mathcal{G})$ is a tcc in $\mathcal{G}$ if and only if $S$
is a bidirectional clique in $G_{R}$.

######  Proof 2.2.

Assume $S$ is a tcc in $\mathcal{G}$. Then for each pair of distinct vertices
$u,v\in V(\mathcal{G})$ we have that $u$ reaches $v$ and $v$ reaches $u$. As
$G_{R}$ represents the reachability relation of $\mathcal{G}$, we hence have
$(u,v)\in A(G_{R})$ and $(v,u)\in A(G_{R})$. Hence, $S$ forms a bidirectional
clique in $R_{G}$.

For the other direction, assume $S$ is a bidirectional clique in $G_{R}$.
Hence, for each pair of distinct vertices $u,v\in V(G_{R})$, we have that
$(u,v)\in A(G_{R})$ and $(v,u)\in A(G_{R})$. As $R_{G}$ represents the
reachability relation of $\mathcal{G}$, we have that $u$ reaches $v$ and $v$
reaches $u$ in $\mathcal{G}$. Hence, $S$ forms a temporal connected component
in $\mathcal{G}$.

######  Lemma 2.3.

Let $G$ be a transitive directed graph. Then every vertex set $S\subseteq
V(G)$ is a bidirectional clique in $G$ if and only if each pair of vertices of
$S$ can reach each other.

######  Proof 2.4.

First, assume $S\subseteq V(G)$ is a bidirectional clique in $G$. Then, for
each pair of vertices $u,v\in V(G)$ we have that $(u,v),(v,u)\in A(G)$ and,
hence, $u$ and $v$ can reach each other.

Next, assume $S\subseteq V(G)$ is not a bidirectional clique in $G$ and let
$u,v$ be two vertices in $S$ for which $(u,v)\notin A(G)$. For the sake of
contradiction, assume that each pair of vertices in $S$ can reach each other.
Then, there exists a path $w_{1},w_{2},\dots w_{\ell}$ such that $w_{1}=u$ and
$w_{\ell}=v$. By the assumption that $G$ is transitive, this implies that
$(u,v)\in G$; a contradiction.

Note that this implies the following.

######  Corollary 2.5.

Let $G$ be a transitive directed graph. Then every scc in $G$ is also a
maximal bidirectional clique and vice versa.

The previous observations thereby imply that both Open-TCC and Closed-TCC can
be solved in polynomial time on temporal graphs with transitive reachability
graphs.

##  3 Vertex-Deletion Distance to Transitivity

We first focus on the parameter $\delta_{\mathrm{vd}}$. Note that computing
this parameter is NP-hard: In a strict temporal graph $\mathcal{G}$ with
lifetime 1, the reachability graph $G_{R}$ of $\mathcal{G}$ is exactly the
directed graph obtained from orienting each edge of the underlying graph in
both directions. Hence, on such a temporal graph, computing
$\delta_{\mathrm{vd}}$ is exactly the cluster vertex deletion number of the
underlying graph, that is, the minimum size of any vertex set to remove, such
that no induced path of length 2 remains. Since computing the latter parameter
is NP-hard [22], this hardness also translates to computing the parameter
$\delta_{\mathrm{vd}}$.

Moreover, note that computing this parameter can be done similarly to
computing the cluster vertex deletion number of a graph: If a directed graph
$G=(V,A)$ is not transitive, then there are vertices $u,v,$ and $w$ in $V$,
such that $(u,v)$ and $(v,w)$ are arcs of $A$ and $(u,w)$ is not an arc of
$A$. Hence, each transitivity modulator for $G$ has to contain at least one of
the vertices $u,v,$ or $w$. This implies, that a standard branching algorithm
that considers each of these three vertices to be removed from the graph to
obtain a transitive graph, finds a minimum size transitivity modulator in
$3^{\delta_{\mathrm{vd}}}\cdot n^{\mathcal{O}(1)}$ time.

######  Proposition 3.1.

Let $\mathcal{G}$ be a temporal graph with reachability graph $G_{R}$. Then we
can compute a minimal set $S\subseteq V(\mathcal{G})$ of size
$\delta_{\mathrm{vd}}$ such that $G_{R}[V\setminus S]$ is transitive in time
$3^{\delta_{\mathrm{vd}}}\cdot n^{\mathcal{O}(1)}$.

Based on this result, we now present an FPT-algorithm for Open TCC when
parameterized by $\delta_{\mathrm{vd}}$.

######  Lemma 3.2.

Let $I:=(\mathcal{G},k)$ be an instance of Open-TCC with reachability graph
$G_{R}$. Let $S$ be a given transitivity modulator of $G_{R}$. Then, we can
solve $I$ in time $2^{|S|}\cdot n^{\mathcal{O}(1)}$.

######  Proof 3.3.

By Lemma 2.5, every scc in $G_{R}[V\setminus S]$ is a bidirectional clique,
since $S$ is a transitivity modulator for $G_{R}$. Lemma 2.1 then implies that
each tcc $C$ in $\mathcal{G}$ with $C\cap S=\emptyset$ is an scc in
$G_{R}[V\setminus S]$ and vice versa.

The FPT-algorithm then works as follows: We iterate over all subsets
$S^{\prime}$ of $S$ with the idea to find a tcc that extends $S^{\prime}$. If
$S^{\prime}$ is not a bidirectional clique in $G_{R}$, we discard the current
set and continue with the next subset of $S$, as no superset of $S^{\prime}$
is a bidirectional clique and thus also not a tcc. Hence, assume that
$S^{\prime}$ is a bidirectional clique. If $S^{\prime}$ has size at least $k$,
$I$ is a trivial yes-instance of Open-TCC. Otherwise, we do the following: Let
$V^{\prime}$ be the vertices of $V\setminus S$ that are bidirectional
connected to every vertex in $S^{\prime}$. As $G_{R}[V\setminus S]$ is
transitive, Section 2 implies that $G_{R}[V^{\prime}]$ is also transitive.
Hence, the sccs in $G_{R}[V^{\prime}]$ correspond to tccs in $\mathcal{G}$ by
Corollary 2.5 and Lemma 2.1. Since every vertex in $S^{\prime}$ is
bidirectional connected to every other vertex in $S^{\prime}\cup V^{\prime}$
in $G_{R}$, for each bidirectional clique $C\subseteq V^{\prime}$ in
$G_{R}[V^{\prime}]$, $C\cup S^{\prime}$ is a tcc in $\mathcal{G}$. Hence, it
remains to check, whether any scc in $G_{R}[V^{\prime}]$ has size at least
$k-|S^{\prime}|$. Figure 1 illustrates the sets $S$, $S^{\prime}$, and
$V^{\prime}$.

Figure 1: Illustration of the algorithm in Lemma 3.2. On the left:
reachability graph $G_{R}$ with transitivity modulator $S$ in gray and the
chosen subset $S^{\prime}\subseteq S$ to extend in blue. On the right: The
subset $S^{\prime}$ together with the vertices $V^{\prime}$ that are
bidirectionally connected to all vertices in $S^{\prime}$.

Finding the strongly connected components of a graph and identifying whether a
set of vertices forms a bidirectional clique can be done in polynomial time.
Hence, our algorithm runs in time $2^{\delta_{\mathrm{vd}}}\cdot
n^{\mathcal{O}(1)}$, since we iterate over each subset $S^{\prime}$ of $S$.

Based on Proposition 3.1 and Lemma 3.2, we thus derive our FPT-algorithm for
Open-TCC when parameterized by $\delta_{\mathrm{vd}}$.

######  Theorem 3.4.

Open-TCC can be solved in $3^{\delta_{\mathrm{vd}}}\cdot n^{\mathcal{O}(1)}$
time.

### Kernelization Lower Bounds

In this section, we show that a polynomial kernel for Open-TCC when
parameterized by $\delta_{\mathrm{vd}}+\mathrm{vc}$ is unlikely, where
$\mathrm{vc}$ is the vertex cover number of the underlying graph. Note that
$\delta_{\mathrm{vd}}$ and $\mathrm{vc}$ are incomparable: On the one hand,
consider a temporal graph $\mathcal{G}$ where the underlying graph $G$ is a
star with leaf set $X\cup Y$ and center $c$, such that the edges from $X$ to
$c$ exist in snapshots $G_{1}$ and $G_{3}$ and the edges from $Y$ to $c$ exist
in snapshot $G_{2}$. Then, each vertex of $X$ can reach each other vertex, but
in the strict setting, no vertex of $Y$ can reach any other vertex of $Y$.
Hence, each minimum transitivity modulator has to contain all vertices of $X$
or all but one vertex of $Y$, which implies that for $|X|=|Y|$,
$\delta_{\mathrm{vd}}\in\Theta(|V(\mathcal{G}))$, whereas the vertex cover
number of $G$ is only $1$. On the other hand, consider a temporal graph
$\mathcal{G}$ with only one snapshot $G_{1}$, such that $G_{1}$ is a clique.
Then, the underlying graph of $\mathcal{G}$ is exactly $G_{1}$ and has a
vertex cover number of $|V(\mathcal{G})|-1$, but the strict reachability graph
of $\mathcal{G}$ is a bidirectional clique, which is a transitive graph.
Hence, $\delta_{\mathrm{vd}}(\mathcal{G})=0$.

We now present our kernelization lower bound for the strict undirected version
of Open-TCC.

######  Theorem 3.5.

The strict undirected version of Open-TCC does not admit a polynomial kernel
when parameterized by $\mathrm{vc}+\delta_{\mathrm{vd}}+k$, unless
$\textsf{NP}\subseteq\textsf{coNP/poly}$, where $\mathrm{vc}$ denotes the
vertex cover number of the underlying graph.

######  Proof 3.6.

This result immediately follows from the known [21] reduction from Clique
which, in fact, is as a polynomial parameter transformation.

Next, we present the same lower bound for both directed versions of Open-TCC.

######  Theorem 3.7.

The directed version of Open-TCC does not admit a polynomial kernel when
parameterized by $\mathrm{vc}+\delta_{\mathrm{vd}}+k$, unless
$\textsf{NP}\subseteq\textsf{coNP/poly}$, where $\mathrm{vc}$ denotes the
vertex cover number of the underlying graph. This holds both for the strict
and the non-strict version of the problem.

######  Proof 3.8.

Again, we present a polynomial parameter transformation from Clique.

Recall that Clique does not admit a polynomial kernel when parameterized by
the size of a give minimum size vertex cover $S$ of $G$ plus $k$, unless
$\textsf{NP}\subseteq\textsf{coNP/poly}$ [12]. This holds even if $G[S]$ is
$(k-1)$-partite [20], which implies that each clique of size $k$ in $G$
contains exactly $k-1$ vertices of $S$ and exactly one vertex of $V\setminus
S$, since $V\setminus S$ is an independent set.

#### Construction.

Let $I:=(G:=(V,E),k)$ be an instance of Clique and let $S$ be a given minimum
size vertex cover $S$ of $G$, such that $G[S]$ is $(k-1)$-partite. Assume that
$k>6$.

We obtain an equivalent instance of Open-TCC in two steps: First, we perform
an adaptation of a known reduction [6] from the instance $(G[S],k-1)$ of
Clique to an instance $(\widetilde{\mathcal{G}},k-1)$ of the directed version
of Open-TCC where each sufficiently large (of size at least $5$) vertex set
$X$ of $\widetilde{\mathcal{G}}$ is a tcc in $\widetilde{\mathcal{G}}$ if and
only if $X$ is a clique in $G[S]$. Second, we extend $\widetilde{\mathcal{G}}$
by the vertices of $V\setminus S$ and some additional connectivity-gadgets, to
ensure that the resulting temporal graph has a tcc of size $k$ if and only if
there is a vertex from $V\setminus S$ for which the neighborhood in $G$
contains a clique of size $k-1$.

$u$$v$$u$$v$$e_{uv}$$e_{vu}$4545 Figure 2: For two adjacent vertices $u$ and
$v$ of $S$ the vertices and arcs added to the temporal graph
$\widetilde{\mathcal{G}}$ in the proof of Theorem 3.7.

Let $(\widetilde{\mathcal{G}},k-1)$ be the instance of Open-TCC constructed as
follows: We initialize $\widetilde{\mathcal{G}}$ as an edgeless temporal graph
of lifetime $5$ with vertex set $S\cup\\{e_{uv},e_{vu}\mid\\{u,v\\}\in
E_{G}(S)\\}$. Next, for each edge $\\{u,v\\}\in E$, we add the arcs
$(u,e_{uv})$ and $(v,e_{vu})$ to time step 4 and add the arcs $(e_{uv},v)$ and
$(e_{vu},u)$ to time step 5. This completes the construction of
$\widetilde{\mathcal{G}}$. An example of the arcs added to
$\widetilde{\mathcal{G}}$ is shown in Figure 2. Note that the first three
snapshots of $\widetilde{\mathcal{G}}$ are edgeless. This construction is an
adaptation of the reduction presented by Bhadra and Ferreira [6] to the case
of directed temporal graphs. Note that the temporal graph
$\widetilde{\mathcal{G}}$ has the following properties that we make use of in
our reduction:

  1. 1)

$\widetilde{\mathcal{G}}$ is a proper and simple directed temporal graph,

  2. 2)

the vertex set $\mathcal{V}$ of $\widetilde{\mathcal{G}}$ has size
$\mathcal{O}(|S|^{2})$ and contains all vertices of $S$,

  3. 3)

each tcc of size at least $k-1$ in $\widetilde{\mathcal{G}}$ contains only
vertices of $S$, and

  4. 4)

each vertex set $X\subseteq S$ of size at least $k-1$ is a tcc in
$\widetilde{\mathcal{G}}$ if and only if $X$ is a clique in $G[S]$.

Note that the two last properties imply that the largest tcc of
$\widetilde{\mathcal{G}}$ has size at most $k-1$, since $G[S]$ is
$(k-1)$-partite.

Next, we describe how to extend the temporal graph $\widetilde{\mathcal{G}}$
to obtain a temporal graph $\mathcal{G}^{\prime}$ which has a tcc of size $k$
if and only if $I$ is a yes-instance of Clique. Let $n:=|V|$. Moreover, let
$\mathcal{G}^{\prime}$ be a copy of $\widetilde{\mathcal{G}}$. We extend the
vertex set of $\mathcal{G}^{\prime}$ by all vertices of $V\setminus S$, and a
vertex ${v}_{\mathrm{in}}$ for each vertex $v\in S$.

For each vertex $v\in S$, we add the arc $({v}_{\mathrm{in}},v)$ to time step
$3$. For each vertex $v\in S$ and each neighbor $w\in V\setminus S$ of $v$ in
$G$, we add the arc $(v,w)$ to time step $2$ and the arc
$(w,{v}_{\mathrm{in}})$ to time step $1$. This completes the construction of
$\mathcal{G}^{\prime}$. Let $V^{\prime}$ denote the newly added vertices, that
is, $V^{\prime}:=(V\setminus S)\cup\\{{v}_{\mathrm{in}}\mid v\in S\\}$.

Next, we show that there is a clique of size $k$ in $G$ if and only if there
is a tcc of size $k$ in $\mathcal{G}^{\prime}$.

$(\Rightarrow)$ Let $K\subseteq V$ be a clique of size $k$ in $G$. We show
that $K$ is a tcc in $\mathcal{G}^{\prime}$. As discussed above, $K$ contains
exactly $k-1$ vertices of $S$ and exactly one vertex $w^{*}$ of $V\setminus
S$. By construction of $\widetilde{\mathcal{G}}$, $K\setminus\\{w^{*}\\}$ is a
tcc in $\widetilde{\mathcal{G}}$ and thus also a tcc in
$\mathcal{G}^{\prime}$. It thus remains to show that each vertex
$K\setminus\\{w^{*}\\}$ can reach vertex $w^{*}$ in $\mathcal{G}^{\prime}$ and
vice versa. Since each vertex of $K\setminus\\{w^{*}\\}$ is adjacent to
$w^{*}$ in $G$, by construction, $w^{*}$ is an out-neighbor of each vertex of
$K\setminus\\{w^{*}\\}$ in $\mathcal{G}^{\prime}$. Hence, it remains to show
that $w^{*}$ can reach each vertex of $K\setminus\\{w^{*}\\}$ in
$\mathcal{G}^{\prime}$. Let $v$ be a vertex of $K\setminus\\{w^{*}\\}$. Since
$v$ is adjacent to $w^{*}$ in $G$, there is an arc $(w^{*},{v}_{\mathrm{in}})$
in $\mathcal{G}^{\prime}$ that exists at time step $1$. Hence, there is a
temporal path from $w^{*}$ to $v$ in $\mathcal{G}^{\prime}$, since the arc
$({v}_{\mathrm{in}},v)$ exists at time step $3$. Concluding, $K$ is a tcc in
$\mathcal{G}^{\prime}$.

$(\Leftarrow)$ Let $X$ be a tcc of size $k$ in $\mathcal{G}^{\prime}$. We show
that $X$ is a clique of size $k$ in $G$. To this end, we first show that $X$
contains only vertices of $V$. Afterwards, we show that $X$ is a clique in
$G$.

To show that $X$ contains only vertices of $V$, we first analyze the
reachability of vertices of $V(\mathcal{G}^{\prime})$. For a vertex $v\in
V(\mathcal{G}^{\prime})$, we denote

  * •

by $\mathrm{out}^{\min}_{v}$ the smallest time label of any arc exiting $v$
and

  * •

by $\mathrm{in}^{\max}_{v}$ the largest time label of any arc entering $v$.

Note that a vertex $v$ cannot reach a distinct vertex $w$ in
$\mathcal{G}^{\prime}$ if $\mathrm{in}^{\max}_{w}<\mathrm{out}^{\min}_{v}$.
Table 1 show for each vertex $v\in V(\mathcal{G}^{\prime})$ a lower bound for
$\mathrm{out}^{\min}_{v}$ and an upper bound for $\mathrm{in}^{\max}_{v}$.

Table 1: For each vertex $v\in V(\mathcal{G}^{\prime})$ a lower bound for $\mathrm{out}^{\min}_{v}$ and an upper bound for $\mathrm{in}^{\max}_{v}$. | $\mathrm{out}^{\min}_{v}$ | $\mathrm{in}^{\max}_{v}$
---|---|---
$v\in S$ | 2 | 5
$v\in V(\widetilde{\mathcal{G}})\setminus S$ | 4 | 5
$v\in V\setminus S$ | 1 | 2
$v\in\\{{u}_{\mathrm{in}}\mid u\in S\\}$ | 3 | 1

Based on Table 1, we can derive the following properties about reachability in
$\mathcal{G}^{\prime}$.

######  Claim 2.

  1. a)

No vertex of $V(\widetilde{\mathcal{G}})\setminus S$ can reach any vertex of
$V^{\prime}$ in $\mathcal{G}^{\prime}$.

  2. b)

No vertex of $\\{{v}_{\mathrm{in}}\mid v\in S\\}$ can reach any other vertex
of $\\{{v}_{\mathrm{in}}\mid v\in S\\}$ in $\mathcal{G}^{\prime}$.

  3. c)

No vertex of $\\{{v}_{\mathrm{in}}\mid v\in S\\}$ can reach any vertex of
$V\setminus S$ in $\mathcal{G}^{\prime}$.

  4. d)

No vertex of $S$ can reach any vertex of $\\{{v}_{\mathrm{in}}\mid v\in S\\}$
in $\mathcal{G}^{\prime}$.

  5. e)

No vertex of $V\setminus S$ can reach any other vertex of $V\setminus S$ in
$\mathcal{G}^{\prime}$.

Based on Table 1, we derive Items a) to d). It remains to show Item e). To
this end, observe that each arc with a vertex of $V\setminus S$ as source has
a vertex of $\\{{v}_{\mathrm{in}}\mid v\in S\\}$ as sink. Due to Item c, no
vertex of $\\{{v}_{\mathrm{in}}\mid v\in S\\}$ can reach any vertex of
$V\setminus S$ in $\mathcal{G}^{\prime}$. Hence, no vertex $V\setminus S$ can
reach any other vertex of $V\setminus S$ in $\mathcal{G}^{\prime}$. This
implies that Item e) holds.

Since $X$ is a tcc in $\mathcal{G}^{\prime}$, 2 implies that $X$ contains at
most one vertex of $V\setminus S$ (due to Item e) and at most one vertex of
$\\{{v}_{\mathrm{in}}\mid v\in S\\}$ (due to Item b). In other words, $X$
contains at most two vertices of $V^{\prime}$. Since $k>6$, this then implies
that $X$ contains at least one vertex of $V(\widetilde{\mathcal{G}})$. 2 thus
further implies that $X$ contains no vertex of $\\{{v}_{\mathrm{in}}\mid v\in
S\\}$ (due to Items a and d). This then implies that $X$ contains at least
$k-1$ vertices of $V(\widetilde{\mathcal{G}})$.

To show that $X$ contains only vertices of $V$ and is a clique in $G$ we now
show that the reachability between any two vertices of
$V(\widetilde{\mathcal{G}})$ in $\mathcal{G}^{\prime}$ is the same as in
$\widetilde{\mathcal{G}}$. Let $P$ be a temporal path between two distinct
vertices of $V(\widetilde{\mathcal{G}})$ in $\mathcal{G}^{\prime}$. We show
that $P$ is also a temporal path in $\widetilde{\mathcal{G}}$. Assume towards
a contradiction that this is not the case. Hence, $P$ visits at least one
vertex of $V^{\prime}$. Since no vertex of $V(\widetilde{\mathcal{G}})$ can
reach any vertex of $\\{{v}_{\mathrm{in}}\mid v\in S\\}$ (due to Items a and
d), $P$ visits no vertex of $\\{{v}_{\mathrm{in}}\mid v\in S\\}$. Moreover,
since each vertex of $V\setminus S$ has only out-neighbors in
$\\{{v}_{\mathrm{in}}\mid v\in S\\}$, $P$ visits no vertex of $V\setminus S$
either. Consequently, $P$ contains no vertex of $V^{\prime}$; a contradiction.

Hence, $P$ is a temporal path in $\widetilde{\mathcal{G}}$, which implies that
for each vertex set $Y\subseteq V(\widetilde{\mathcal{G}})$, $Y$ is a tcc in
$\widetilde{\mathcal{G}}$ if and only if $Y$ is a tcc in
$\mathcal{G}^{\prime}$. Recall that $X$ contains at least $k-1$ vertices of
$V(\widetilde{\mathcal{G}})$. Since the largest tcc in
$\widetilde{\mathcal{G}}$ has size at most $k-1$ and each tcc of size $k-1$ in
$\widetilde{\mathcal{G}}$ is a clique in $G$, this implies that $X\cap
V(\widetilde{\mathcal{G}})$ is a clique of size $k-1$ in $G[S]$. Since $X$
contains no vertex of $\\{{v}_{\mathrm{in}}\mid v\in S\\}$, this implies that
$X$ contains exactly one vertex $w^{*}$ of $V\setminus S$. Hence, it remains
to show that each vertex $v\in X\setminus\\{w^{*}\\}$ is adjacent to $w^{*}$
in $G$. Since $X$ is a tcc in $\mathcal{G}^{\prime}$, $v$ can reach $w^{*}$ in
$\mathcal{G}^{\prime}$. By construction and illustrated in Table 1,
$\mathrm{out}^{\min}_{v}\geq 2\geq\mathrm{in}^{\max}_{w^{*}}$. Since $v$
reaches $w^{*}$ and $\mathcal{G}^{\prime}$ is a proper temporal graph, the arc
$(v,w^{*})$ is contained in $\mathcal{G}^{\prime}$. By construction, this
implies that $v$ and $w^{*}$ are adjacent in $G$. Consequently, $X$ is a
clique in $G$. This completes the correctness proof of the reduction.

#### Parameter bounds.

It thus remains to show that $\delta_{\mathrm{vd}}(\mathcal{G}^{\prime})$ and
the vertex cover of the underlying graph of $\mathcal{G}^{\prime}$ are at most
$|S|^{\mathcal{O}(1)}$ each. Let
$V^{*}:=V(\mathcal{G}^{\prime})\setminus(V\setminus S)$. Note that $V^{*}$ has
size $|V(\widetilde{\mathcal{G}})|+|S|\in\mathcal{O}(|S|^{2})$ and is a vertex
cover of the underlying graph of $\mathcal{G}^{\prime}$. Hence, the vertex
cover number of the underlying graph of $\mathcal{G}^{\prime}$ is
$\mathcal{O}(|S|^{2})$. To show the parameter bounds, it thus suffices to show
that $V^{*}$ is a transitivity modulator of the reachability graph $G_{R}$ of
$\mathcal{G}^{\prime}$. Due to 2, $G_{R}-V^{*}=G_{R}[V\setminus S]$ is an
independent set. Consequently, $V^{*}$ is a transitivity modulator of $G_{R}$.
Hence, $\delta_{\mathrm{vd}}(\mathcal{G}^{\prime})\in\mathcal{O}(|S|^{2})$. By
the fact that Clique does not admit a polynomial kernel when parameterized by
$|S|+k$, unless $\textsf{NP}\subseteq\textsf{coNP/poly}$, Open-TCC does not
admit a polynomial kernel when parameterized by
$\delta_{\mathrm{vd}}(\mathcal{G}^{\prime})$ plus the vertex cover number of
the underlying graph of $\mathcal{G}^{\prime}$ plus $k$, unless
$\textsf{NP}\subseteq\textsf{coNP/poly}$.

Note that our kernelization lower bounds do not include the non-strict
undirected version of Open-TCC. An modification of Theorem 3.7 seems
difficult, unfortunately. This is due to the fact that undirected edges can be
traversed in both direction, which makes it very difficult to limit the
possible reachable vertices in the temporal graph, while preserving a small
transitivity modulator.

##  4 Arc-Modification Distance to Transitivity - A Polynomial Kernel

Next, we focus on the parameterized complexity of Open-TCC when parameterized
by the size of a given arc-modification set towards a transitive reachability
graph. As discussed earlier, for each arc-modification set $M$ towards a
transitive reachability graph, $\delta_{\mathrm{vd}}$ does not exceed
$2\cdot|M|$, since removing the endpoints of all edges of $M$ results in a
transitivity modulator. This implies the following due to Theorem 3.4 and the
fact that a minimum size arc-modification set towards a transitive graph can
be computed in $2.57^{\delta_{\mathrm{am}}}\cdot n^{\mathcal{O}(1)}$ time
[25].

######  Corollary 4.1.

Open-TCC can be solved in $4^{\delta_{\mathrm{am}}}\cdot n^{\mathcal{O}(1)}$
time.

In the remainder of this section, we thus consider this parameter with respect
to kernelization algorithms. In contrast to parameterizations by
$\delta_{\mathrm{vd}}$, we now show that a polynomial kernelization algorithm
can be obtained for Open-TCC when parameterized by the size of a given arc-
modification set towards a transitive reachability graph.

In fact, we show an even stronger result, since our kernelization algorithm
does not need to know the actual arc-modification set but only its endpoints.
To formulate this more general result, we need the following definition: Let
$G=(V,A)$ be a directed graph. A transitivity modulator $S\subseteq V$ of $G$
is called  _inherent_ , if there is an arc-modification set $M$ with
$M\subseteq S\times S$ for which $(V,A\Delta M)$ is a transitive graph. Note
that the set of endpoint of an arc-modification set towards a transitive graph
always forms an inherent transitivity modulator.

######  Theorem 4.2.

Let $I=(\mathcal{G},k)$ be an instance of Open-TCC and let $G_{R}=(V,A)$ be
the reachability graph of $\mathcal{G}$. Moreover, let $B\subseteq V$ be an
inherent transitivity modulator of $G_{R}$. Then, for each version of Open-
TCC, one can compute in polynomial time an equivalent instance of total size
$\mathcal{O}(|B|^{3})$.

$\widehat{G}$$G^{\prime}$ Figure 3: Left: the original instance of Clique from
Theorem 4.2 constructed from the reachability graph of the considered temporal
graph. Right: the obtained compressed instance of Clique after exhaustive
application of all reduction rules. In both parts, the blue vertices are the
vertices from the inherent transitivity modulator $B$ and the cycles at the
bottom indicate the white clusters. Note that in both graphs, each blue vertex
has neighbors in at most one white cluster (see 4). Intuitively, RR 1 ensures
that small clusters are removed, RR 1 and RR 2 ensure that there are no
isolated white clusters, and RR 3 reduces the size of each white cluster to at
most $|B|+1$.

######  Proof 4.3.

We first present a compression to Clique. Let $\widehat{G}=(V,E)$ be an
undirected graph that contains an edge $\\{u,v\\}$ if and only if $(u,v)$ and
$(v,u)$ are arcs of $G_{R}$. Due to Lemma 2.1, $I$ is a yes-instance of Open-
TCC if and only if $(\widehat{G},k)$ is a yes-instance of Clique. Let
$W:=V\setminus B$. We call the vertices of $B$  _blue_ and the vertices of $W$
_white_. Note that $G_{R}[W]$ is a transitive graph, since $B$ is a
transitivity modulator of $G_{R}$. Moreover, there exists an arc set
$M\subseteq B\times B$ such that $G^{\prime}_{R}=(V,A\Delta M)$ is transitive,
since $B$ is an inherent transitivity modulator of $G_{R}$. In the following,
we present reduction rules to remove vertices from $\widehat{G}$ to obtain an
equivalent instance $(G^{\prime},k^{\prime})$ of Clique with
$\mathcal{O}(|B|^{2})$ vertices and where $G^{\prime}$ is an induced subgraph
of $\widehat{G}$. The graphs $\widehat{G}$ and $G^{\prime}$ are conceptually
depicted in Figure 3.

To obtain this smaller instance of Clique, we initialize $G^{\prime}$ as a
copy of $\widehat{G}$ and $k^{\prime}$ as $k$ and exhaustively applying three
reduction rules. Our first two reduction rules are the following:

  * •

RR 1: Remove a vertex $v$ from $G^{\prime}$, if $v$ has degree less than
$k^{\prime}-1$ in $G^{\prime}$.

  * •

RR 2: If a white vertex has at least $k^{\prime}-1$ white neighbors in
$G^{\prime}$, output a constant size yes-instance.

Note that the first reduction rule is safe, since no vertex of degree less
than $k^{\prime}-1$ can be part of a clique of size at least $k^{\prime}$.
Moreover, each connected component in $G^{\prime}$ has size at least
$k^{\prime}$ after this reduction rule is exhaustively applied. The safeness
of the second reduction rule relies on the following observation.

######  Claim 3.

If two white vertices $u$ and $v$ are adjacent in $G^{\prime}$, then they are
real twins in $G^{\prime}$. That is, $N_{G^{\prime}}[u]=N_{G^{\prime}}[v]$.

Assume that $u$ and $v$ are adjacent in $G^{\prime}$ and assume towards a
contradiction that there is a vertex $w$ in $G^{\prime}$ which is adjacent to
$u$ in $G^{\prime}$ but not adjacent to $v$ in $G^{\prime}$. Since $w$ and $v$
are not adjacent in $G^{\prime}$, $G_{R}$ contains at most one of the arcs
$(w,v)$ or $(v,w)$. Assume without loss of generality that $(w,v)$ is not an
arc of $G_{R}$. Since $u$ is adjacent to both $v$ and $w$ in $G^{\prime}$,
$G_{R}$ contains the arcs $(v,u)$ and $(u,w)$. Recall that both $u$ and $v$
are white vertices. This implies that the arc-modification set $M$ contains no
arc incident with any of these two vertices. Hence, $M$ contains none of the
arcs of $\\{(v,u),(u,w),(v,w)\\}$, which implies that
$G_{R}^{\prime}=(V,A\Delta M)$ is not a transitive graph; a contradiction.

Note that this implies that each connected component in $G^{\prime}[W]$ is a
clique of real twins in $G^{\prime}$. We call each such connected component in
$G^{\prime}[W]$ a  _white cluster_.

Note that after exhaustive applications of the first two reduction rules, each
white cluster has size at most $k^{\prime}-1$ and each connected component in
$G^{\prime}$ has size at least $k^{\prime}$. This implies that each connected
component in $G^{\prime}$ contains at least one blue vertex. Since
$G^{\prime}$ contains at most $|B|$ blue vertices, this implies that
$G^{\prime}$ has at most $|B|$ connected components.

In the following, we show that no blue vertex has neighbors in more than one
white cluster. This then implies that $G^{\prime}$ contains at most $|B|\cdot
k^{\prime}$ vertices. In a final step, we then show how to reduce the value of
$k^{\prime}$.

######  Claim 4.

No blue vertex has neighbors in more than one white cluster.

Assume towards a contradiction that there is a blue vertex $w$ which is
adjacent to two white vertices $u$ and $v$ in $G^{\prime}$, such that $u$ and
$v$ are not part of the same white cluster. Since $u$ and $v$ are not part of
the same white cluster, $u$ and $v$ are not adjacent in $G^{\prime}$ due to 3.
This implies that $G_{R}$ contains at most one of the arcs $(u,v)$ or $(v,u)$.
Assume without loss of generality that $(u,v)$ is not an arc of $G_{R}$. Since
$w$ is adjacent to both $u$ and $v$ in $G^{\prime}$, $G_{R}$ contains the arcs
$(u,w)$ and $(w,v)$. By the fact that both $u$ and $v$ are white vertices, $M$
contains no arc of $\\{(u,w),(w,v),(u,v)\\}$, which implies that
$G_{R}^{\prime}=(V,A\Delta M)$ is not a transitive graph; a contradiction.

As mentioned above, this implies that $G^{\prime}$ contains at most $|B|\cdot
k^{\prime}$ vertices. Next, we show how to reduce the size of the white
clusters if $k^{\prime}>|B|$. To this end, we introduce our last reduction
rule:

  * •

RR 3: If $k^{\prime}>|B|+1$, remove an arbitrary white vertex from each white
cluster and reduce $k^{\prime}$ by 1.

Note that RR 3 is safe: If $k^{\prime}>|B|+1$, a clique of size $k^{\prime}$
in $G^{\prime}$ has to contain at least two white vertices, since $G^{\prime}$
contains at most $|B|$ blue vertices. Since no clique in $G^{\prime}$ can
contain vertices of different white clusters, we reduce the size of a maximal
clique of size at least $k^{\prime}$ in $G^{\prime}$ by exactly one, when
removing one vertex of each white cluster.

Hence, after all reduction rules are applied exhaustively, the resulting
instance $(G^{\prime},k^{\prime})$ of Clique contains at most $|B|$ blue
vertices and at most $|B|$ white clusters. Each such white cluster hast size
at most $|B|+1$. This implies that the resulting graph $G^{\prime}$ contains
$\mathcal{O}(|B|^{2})$ vertices and $\mathcal{O}(|B|^{3})$ edges, since each
vertex has degree $\mathcal{O}(|B|)$.

Based on known polynomial-time reduction [6], we can compute for an instance
$(G^{*},k^{*})$ of Clique, an equivalent instance $(\mathcal{G}^{*},k^{*})$ of
Open-TCC, where $\mathcal{G}^{*}$ is a proper temporal graph and has
$\mathcal{O}(n+m)$ vertices and edges, where $n$ and $m$ denote the number of
vertices and the number of edges of $G^{*}$, respectively. Since $G^{\prime}$
has $\mathcal{O}(|B|^{2})$ vertices and $\mathcal{O}(|B|^{3})$ edges, this
implies that we can obtain an equivalent instance of Open-TCC of total size
$\mathcal{O}(|B|^{3})$ in polynomial time. By the fact that $\mathcal{G}^{*}$
is a proper temporal graph, this works for all problem versions of Open-TCC.
This implies the stated kernelization result.

Based on the fact that the set $B$ of endpoints of any arc-modification set
$M$ towards a transitive graph is an inherent transitivity modulator of size
at most $2\cdot|M|$, this implies the following for kernelization algorithms
with respect to arc-modification sets towards a transitive graph.

######  Theorem 4.4.

Let $I=(\mathcal{G},k)$ be an instance of Open-TCC and let $G_{R}=(V,A)$ be
the reachability graph of $\mathcal{G}$. Moreover, let $M\subseteq V\times V$
be a set of arcs such that $G^{\prime}_{R}=(V,A\Delta M)$ is transitive. Then,
for each version of Open-TCC, one can compute in polynomial time an equivalent
instance of total size $\mathcal{O}(|M|^{3})$.

Moreover, if the arc-modification set $M$ only adds arcs to the reachability
graph, we can obtain the further even better kernelization result.

######  Lemma 4.5.

Let $I=(\mathcal{G},k)$ be an instance of Open-TCC and let $G_{R}=(V,A)$ be
the reachability graph of $\mathcal{G}$. Moreover, let $M\subseteq V\times V$
be a set with $A\cap M=\emptyset$ of arcs such that $G^{\prime}_{R}=(V,A\Delta
M)$ is transitive. Then, for each version of Open-TCC, one can compute in
polynomial time an equivalent instance of total size $\mathcal{O}(|M|^{2})$.

######  Proof 4.6.

First, we perform the compression to Clique described in Theorem 4.2. Let $B$
be the endpoints of the arcs of $M$ and let $W:=V\setminus B$. Note that $B$
is a inherent transitivity modulator of $G_{R}$ of size at most $2\cdot|M|$.

Again, we call the vertices of $B$  _blue_ and the vertices of $W$  _white_.
Let $(G^{\prime},k^{\prime})$ be the instance of Clique resulting after
exhaustively applying the reduction rules RR 1, RR 2, and RR 3 to the instance
$(\widehat{G},k)$ (see Theorem 4.2). Recall that $G^{\prime}$ contains at most
$|B|$ blue vertices and at most $|B|$ white clusters. Moreover, each white
cluster has size at most $|B|+1$, no vertices of different white clusters are
adjacent, and each blue vertex has neighbors in at most one white cluster.

In the following, we show how to improve the kernel-size, knowing that $M$
contains no arc of $G_{R}$. To this end, we observe that each white vertex is
adjacent to each vertex of its connected component in $G^{\prime}$.

######  Claim 5.

Let $u$ be a white vertex and let $C$ be the connected component of $u$ in
$G^{\prime}$. Then, $u$ is adjacent to each other vertex of $C$.

Assume towards a contradiction that there is a vertex $w$ in $C$ that is not
adjacent to $u$. Since $C$ is a connected component in $G^{\prime}$, this
implies that there is a vertex in $C$ that has distance exactly two with $u$.
We can assume without loss of generality that $w$ is this vertex, that is,
there is a vertex $v$ in $C$ that is adjacent to both $u$ and $w$. This
implies that $G_{R}$ contains at most one of the arcs $(u,w)$ or $(w,u)$.
Assume without loss of generality that $(u,w)$ is not an arc of $G_{R}$. Since
$v$ is adjacent to both $u$ and $w$ in $G^{\prime}$, $G_{R}$ contains the arcs
$(u,v)$ and $(v,w)$. By the fact that $u$ is a white vertex, $M$ does not
contain the arc $(u,w)$. Moreover, since $M$ contains no arc of
$\\{(u,v),(v,w)\\}$, we obtain that $G_{R}^{\prime}=(V,A\Delta M)$ is not a
transitive graph; a contradiction. Note that this further implies that if two
blue vertices are adjacent in $G^{\prime}$, then both of these vertices have
the same white neighbors. Based on this observation, we now show how to obtain
an equivalent instance $(G^{\prime\prime},k^{\prime\prime})$ of Clique, where
$G^{\prime\prime}$ has only $\mathcal{O}(|B|)$ vertices.

Let $C_{1},\dots,C_{\ell}$ be the connected components of $G^{\prime}$ and for
each $i\in[1,\ell]$, let $\alpha_{i}$ denote the number of white vertices of
$C_{i}$, that is, $\alpha_{i}:=|C_{i}\cap W|$. We obtain the graph
$G^{\prime\prime}$ as follows: Initially, we set
$G^{\prime\prime}:=G^{\prime}[B]$. Afterwards, we add a clique $W^{*}$ of size
$\max_{i\in[1,\ell]}\alpha_{i}$ to $G^{\prime\prime}$. We fix some arbitrary
order on the vertices of $W^{*}$ and add for each $i\in[1,\ell]$ an edge
between each blue vertex of $C_{i}$ and each of the first $\alpha_{i}$
vertices of $W^{*}$ to $G^{\prime\prime}$. Finally, we set
$k^{\prime\prime}:=k^{\prime}$. Note that $G^{\prime\prime}$ contains
$\mathcal{O}(|B|)$ vertices and $\mathcal{O}(|B|^{2})$ edges, since the size
of $W^{*}$ is the size of the largest white cluster in $G^{\prime}$, which is
$\mathcal{O}(|B|)$. Based on the above mentioned reduction to Open-TCC and the
fact that $|B|\leq 2\cdot|M|$, we can thus obtain an equivalent instance of
Open-TCC with a proper temporal graph of total size $\mathcal{O}(|M|^{2})$.

To show the correctness of this algorithm it remains to show that $G^{\prime}$
contains a clique of size $k^{\prime}$ if and only if $G^{\prime\prime}$
contains a clique of size $k^{\prime}$.

$(\Rightarrow)$ Let $S$ be a clique of size $k^{\prime}$ in $G^{\prime}$.
Moreover, let $C_{i}$ be the connected component of $G^{\prime}$ that contains
$S$. By construction, the first $\alpha_{i}=|C_{i}\cap W|$ vertices of $W^{*}$
are adjacent to each blue vertex of $S$. Since $S$ is a clique of size
$k^{\prime}$ in $G^{\prime}$, this implies that $(S\cap B)\cup
W^{*}_{\leq\alpha_{i}}$ is a clique of size at least $k^{\prime}$ in
$G^{\prime\prime}$, where $W^{*}_{\leq\alpha_{i}}$ denotes the first
$\alpha_{i}$ vertices of $W^{*}$.

$(\Leftarrow)$ Let $S$ be a clique of size $k^{\prime}$ in $G^{\prime\prime}$.
Since the second reduction rule is exhaustively applied, $k^{\prime}$ exceeds
the size of $W^{*}$. Consequently, $S$ contains at least one blue vertex.
Since the adjacency between blue vertices is the same in both $G^{\prime}$ and
$G^{\prime\prime}$, all white vertices of $S$ belong to the same connected
component of $G^{\prime}$, that is, there is some $i\in[1,\ell]$, such that
$S\cap B\subseteq C_{i}$. Since each vertex of $C_{i}\cap B$ is adjacent only
to $\alpha_{i}=|C_{i}|$ vertices of $W^{*}$, $(S\cap B)\cup(C_{i}\cap W)$ is a
clique of size at least $k^{\prime}$ in $G^{\prime}$.

Hence, if we are given an arc-modification set $M$ of size
$\delta_{\mathrm{am}}$, we can compute a polynomial kernel. Unfortunately,
finding a minimum-size arc-modification set of a given directed graph is NP-
hard [25] and no polynomial-factor approximations are known that run in
polynomial time. Hence, we cannot derive a polynomial kernel for the parameter
$\delta_{\mathrm{am}}$. Positively, if we only consider arc-additions, we can
compute the transitive closure of a given directed graph in polynomial time.
This implies that we can find a minimum-size arc-modification set towards a
transitive reachability graph in polynomial time among all such sets that only
add arcs to to reachability graph. Consequently, we derive the following.

######  Corollary 4.7.

Open-TCC admits a kernel of size $\mathcal{O}(\delta_{\mathrm{aa}}^{2})$,
where $\delta_{\mathrm{aa}}$ denotes the minimum number of necessary arc-
additions to make the respective reachability graph transitive.

##  5 Limits of these Parametrizations for Closed TCCs

So far, the temporal paths that realize the reachability between two vertices
in a tcc could lie outside of the temporal connected component. If we impose
the restriction that those temporal paths must be contained in the tcc, the
problem of finding a large tcc becomes NP-hard even when the reachability
graph is missing only a single arc to become a complete bidirectional clique:
In other words, the problem becomes NP-hard even if
$\delta_{\mathrm{vd}}=\delta_{\mathrm{am}}=1$. On general temporal graphs, all
versions of Closed-TCC are known to be NP-hard [8, 13].

######  Theorem 5.1.

For each version of Closed-TCC, there is a polynomial time self-reduction that
transforms an instance $(\mathcal{G},k)$ with $k>4$ of that version of Closed-
TCC into an equivalent instance $(\mathcal{G}^{\prime},k)$, such that the
reachability graph of $\mathcal{G}^{\prime}$ is missing only a single arc to
be a complete bidirectional clique.

######  Proof 5.2.

Let $I:=(\mathcal{G},k)$ be an instance of Closed-TCC with underlying graph
$G=(V,E)$ and let $L$ be the lifetime of $\mathcal{G}$. Moreover, assume for
simplicity that the vertices of $V$ are exactly the natural numbers from
$[1,n]$ with $n:=|V|$. To obtain an equivalent instance
$I^{\prime}:=(\mathcal{G}^{\prime},k)$ of Closed-TCC, we extends $\mathcal{G}$
as follows: We initialize $\mathcal{G}^{\prime}$ as a copy of $\mathcal{G}$
and for each vertex $v\in V$, we add a new vertex $v^{\prime}$ to
$\mathcal{G}^{\prime}$. Additionally, we add three vertices $x_{1}$, $x_{2}$,
and $x_{3}$ to $\mathcal{G}^{\prime}$. Furthermore, we append $2n+4$ empty
snapshots to the end of $\mathcal{G}^{\prime}$ and add the following edges to
$\mathcal{G}^{\prime}$: For each vertex $v\in V$, we add the edge
$\\{v,v^{\prime}\\}$ to time steps $L+1$ and $L+2n+4$, the edge
$\\{v^{\prime},x_{1}\\}$ to time step $L+1+v$, and the edge
$\\{v^{\prime},x_{3}\\}$ to time step $L+n+3+v$. Finally, we add the edge
$\\{x_{1},x_{2}\\}$ to time step $L+n+2$ and the edge $\\{x_{2},x_{3}\\}$ to
time step $L+n+3$. This completes the construction of $\mathcal{G}^{\prime}$.
An illustration of the additional vertices and edges is given in Figure 4.

$x_{1}$$x_{2}$$x_{3}$$1^{\prime}$$2^{\prime}$$n^{\prime}$$L+n+2$$L+n+3$$1$$L+1,L+2n+4$$2$$L+1,L+2n+4$$n$$L+1,L+2n+4$$L+2$$L+3$$\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ L+n+1$$L+n+4\leavevmode\nobreak\
\leavevmode\nobreak\ $$L+n+5\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ $$L+2n+3$$\mathcal{G}$$\cdots$

Figure 4: An illustration of the additional vertices and edges that are added
to $\mathcal{G}$ in the reduction of Theorem 5.1. Here, $L$ denotes the
lifetime of $\mathcal{G}$ and the labels on the edges indicate in which
snapshots the respective edges exist in the constructed temporal graph.

Before we show the equivalence between the two instances of Closed-TCC, we
first show that the reachability graph $G_{R}^{\prime}$ of
$\mathcal{G}^{\prime}$ only misses a single arc to be a bidirectional clique.

######  Claim 6.

The arc $(x_{3},x_{1})$ is the only arc that is missing in $G_{R}^{\prime}$.

First, we show that $(x_{3},x_{1})$ is not an arc of $G_{R}^{\prime}$. By
construction of $\mathcal{G}^{\prime}$, (i) no edge of $\mathcal{G}^{\prime}$
that is incident with $x_{1}$ exists in any time step larger than $L+n+2$, and
(ii) no edge of $\mathcal{G}^{\prime}$ that is incident with $x_{3}$ exists in
any time step smaller than $L+n+3$. This implies that no temporal path in
$\mathcal{G}^{\prime}$ that starts in $x_{3}$ can reach $x_{1}$. Hence,
$(x_{3},x_{1})$ is not an arc of $G^{\prime}_{R}$.

Next, we show that $G_{R}^{\prime}$ contains all other possible arcs. To this
end, we present strict temporal paths in $\mathcal{G}^{\prime}$ that guarantee
the existence of these arcs in $G_{R}^{\prime}$. Let $u$ and $v$ be vertices
of $V$. Consider the temporal path $P$ that starts in vertex $u$ and traverses

  * •

the edge $\\{u,u^{\prime}\\}$ in time step $L+1$,

  * •

the edge $\\{u^{\prime},x_{1}\\}$ in time step $L+1+u$,

  * •

the edge $\\{x_{1},x_{2}\\}$ in time step $L+n+2$,

  * •

the edge $\\{x_{2},x_{3}\\}$ in time step $L+n+3$,

  * •

the edge $\\{x_{3},v^{\prime}\\}$ in time step $L+n+3+v$, and

  * •

the edge $\\{v^{\prime},v\\}$ in time step $L+2n+4$.

Since each vertex of $V$ is a natural number of $[1,n]$, the times steps in
which these edges are traversed by $P$ are strictly increasing, which implies
that $P$ is a strict temporal path of $\mathcal{G}^{\prime}$. Note that each
suffix and each prefix of $P$ is also a strict temporal path in
$\mathcal{G}^{\prime}$. Hence, this implies that $G_{R}^{\prime}$ contains all
the arcs
$\\{(u,v^{\prime}),(u,v),(u^{\prime},v^{\prime}),(u^{\prime},v)\\}\cup\\{(u^{\prime},x_{1}),(u^{\prime},x_{1}),(x_{1},v^{\prime}),(x_{1},v)\mid
i\in\\{1,2,3\\}\\}\cup\\{(x_{1},x_{3})\\}$. Moreover, since
$\\{x_{1},x_{2}\\}$ and $\\{x_{2},x_{3}\\}$ are edges in
$\mathcal{G}^{\prime}$, $G_{R}^{\prime}$ also contains the arcs
$\\{(x_{1},x_{2}),(x_{2},x_{1}),(x_{2},x_{3}),(x_{3},x_{2})\\}$. This implies
that $(x_{3},x_{1})$ is the unique arc that is missing in $G_{R}^{\prime}$.

Next, we show that $I$ is a yes-instance of Closed-TCC if and only if
$I^{\prime}$ is a yes-instance of Closed-TCC.

$(\Rightarrow)$ This direction follows directly by the fact that
$\mathcal{G}^{\prime}$ is obtained by extending $\mathcal{G}$. Hence, a closed
tcc $S$ of size $k$ in $\mathcal{G}$ is also a closed tcc in
$\mathcal{G}^{\prime}$.

$(\Leftarrow)$ Let $S$ be a closed tcc of size $k$ in $\mathcal{G}^{\prime}$.
Recall that $k>4$. We show that $S$ only contains vertices of $V$. To this
end, we first show that $S$ does not contain $x_{2}$.

######  Claim 7.

The set $S$ does not contain $x_{2}$.

Since $k>4$, $S$ contains at least one vertex $v^{*}$ which is not contained
in $\\{x_{1},x_{2},x_{3}\\}$. Note that due to 6, $S$ contains at most one of
$x_{1}$ and $x_{3}$. We distinguish two cases.

Case 1: $x_{1}$ is not contained in $S$. We show that there is no temporal
path from $v^{*}$ to $x_{2}$ in $\mathcal{G}^{\prime}$ that does not visit
$x_{1}$. This then implies that $x_{2}$ is not contained in $S$. Recall that
$\\{x_{2},x_{3}\\}$ is the unique edge incident with $x_{2}$ in
$\mathcal{G}^{\prime}$ that does not have $x_{1}$ as an endpoint. Moreover,
recall that this edge can only be traversed at time step $L+n+3$. By the fact
that each other edge incident with $x_{3}$ exists only in time steps strictly
greater than $L+n+3$, there is no temporal path from $v^{*}$ to $x_{2}$ in
$\mathcal{G}^{\prime}$ that does not visit $x_{1}$.

Case 2: $x_{3}$ is not contained in $S$. We show that there is no temporal
path from $x_{2}$ to $v^{*}$ in $\mathcal{G}^{\prime}$ that does not visit
$x_{3}$. This then implies that $x_{2}$ is not contained in $S$. Recall that
$\\{x_{1},x_{2}\\}$ is the unique edge incident with $x_{2}$ in
$\mathcal{G}^{\prime}$ that does not have $x_{3}$ as an endpoint. Moreover,
recall that this edge can only be traversed at time step $L+n+2$. By the fact
that each other edge incident with $x_{1}$ exists only in time steps strictly
smaller than $L+n+2$, there is no temporal path from $x_{2}$ to $v^{*}$ in
$\mathcal{G}^{\prime}$ that does not visit $x_{3}$.

Next, we show that the vertex $x_{2}$ is required to have pairwise temporal
paths between distinct vertices of $\\{w^{\prime}\mid w\in V\\}$ in
$\mathcal{G}^{\prime}$.

######  Claim 8.

Let $u$ and $v$ be distinct vertices of $V$ with $u<v$. Then, each temporal
path from $v^{\prime}$ to $u^{\prime}$ in $\mathcal{G}^{\prime}$ visits
$x_{2}$.

Assume towards a contradiction that there is a temporal path $P$ from
$v^{\prime}$ to $u^{\prime}$ in $\mathcal{G}^{\prime}$ that does not visit
$x_{2}$. Since each edge incident with $v^{\prime}$ in $\mathcal{G}^{\prime}$
only exists in time steps strictly larger than $L$, $P$ cannot visit any
vertex $w\in V$. This is due to the fact that $\\{w,w^{\prime}\\}$ is the only
edge incident with $w$ in $\mathcal{G}^{\prime}$ that exists in any time step
strictly larger than $L$.

Since $v^{\prime}$ is only incident with the three edges $\\{v^{\prime},v\\}$,
$\\{v^{\prime},x_{1}\\}$, and $\\{v^{\prime},x_{3}\\}$ in
$\mathcal{G}^{\prime}$, the above implies that $P$ first traverses
$\\{v^{\prime},x_{1}\\}$ or $\\{v^{\prime},x_{3}\\}$. Similarly, the last edge
traversed by $P$ is either $\\{x_{1},u^{\prime}\\}$ or
$\\{x_{3},u^{\prime}\\}$. By construction, the edge $\\{v^{\prime},x_{3}\\}$
only exists at time step $L+2n+3+v$ which is strictly larger than the time
steps in which $\\{x_{1},u^{\prime}\\}$ or $\\{x_{3},u^{\prime}\\}$ exists,
namely time step $L+1+u$ and time step $L+2n+3+u$, respectively. This implies
that $P$ does not traverse the edge $\\{v^{\prime},x_{3}\\}$. Similarly, since
the edge $\\{v^{\prime},x_{1}\\}$ only exists at time step $L+1+v$ which is
strictly larger than the time steps in which $\\{x_{1},u^{\prime}\\}$ exists,
$P$ firstly traverses the edge $\\{v^{\prime},x_{1}\\}$ and lastly traverses
the edge $\\{x_{3},u^{\prime}\\}$.

Since $P$ does not visit $x_{2}$, for some vertex $w\in V$, $P$ secondly
traverses the edge $\\{x_{1},w^{\prime}\\}$, and thirdly traverses the edge
$\\{w^{\prime},x_{3}\\}$. Moreover, since $P$ is a temporal path in
$\mathcal{G}^{\prime}$, the edge $\\{x_{1},w^{\prime}\\}$ exists in a time
step at least as large as the time step in which $\\{v^{\prime},x_{1}\\}$
exists. By definition of $\mathcal{G}^{\prime}$, this implies that $w>v$.
Since $v>u$, this implies that the edge $\\{w^{\prime},x_{3}\\}$ exists only
at time step $L+n+3+w$, which is strictly larger than the time step in which
the edge $\\{x_{3},u^{\prime}\\}$ exists. Hence, $P$ is not a temporal path in
$\mathcal{G}^{\prime}$; a contradiction.

As a consequence, $S$ contains at most one vertex of $\\{w^{\prime}\mid w\in
V\\}$, since $S$ is a closed tcc that does not contain vertex $x_{2}$. Based
on the above two claims, we now show that $S$ contains only vertices of $V$.

######  Claim 9.

Only vertices of $V$ are contained in $S$.

Recall that $S$ contains at most one of $x_{1}$ and $x_{3}$. Due to 7, $S$
does not contain $x_{2}$. By 8, this implies that $S$ contains at most one
vertex of $\\{w^{\prime}\mid w\in V\\}$. Since $k>4$, we have that $S$
contains at least two vertices $u$ and $v$ of $V$.

First, we show that $S$ contains neither vertex $x_{1}$ nor vertex $x_{3}$.
Assume towards a contradiction that $S$ contains $x_{1}$ or $x_{3}$. We
distinguish two cases.

Case 1: $S$ contains $x_{1}$. Note that then $x_{3}$ is not contained in $S$.
Since $S$ contains $x_{1}$, $u$, and $v$, for each $w\in\\{u,v\\}$, there is a
temporal path $P_{w}$ in $\mathcal{G}^{\prime}$ from $x_{1}$ to $w$ that only
visits vertices of $S$. In particular, $P_{w}$ does not visit $x_{3}$. By
construction, each edge incident with $x_{1}$ in $\mathcal{G}^{\prime}$ only
exists in time steps strictly larger than $L$, hence, $P_{w}$ does not
traverse any edge between vertices of $V$. This implies that $P_{w}$ is the
unique temporal path that firstly traverses the edge $\\{x_{1},w^{\prime}\\}$
and secondly traverses the edge $\\{w^{\prime},w\\}$. This implies that
$u^{\prime}$ and $v^{\prime}$ are both contained in $S$. A contradiction to
the fact that $S$ contains at most one vertex of $\\{w^{\prime}\mid w\in
V\\}$.

Case 2: $S$ contains $x_{3}$. This case follows by the same arguments as the
first case, when replacing $x_{1}$ by $x_{3}$ and vice versa.

Hence, we obtain that $S$ contains none of the vertices of
$\\{x_{1},x_{2},x_{3}\\}$. Hence, it remains to show that $S$ contains no
vertex of $\\{w^{\prime}\mid w\in V\\}$. Assume towards a contradiction that
there is a vertex $w\in V$, such that $w^{\prime}$ is contained in $S$. Since
$u$ and $v$ are distinct, assume without loss of generality that $w\neq u$.
Since $S$ contains both $w^{\prime}$ and $u$, there is a temporal path $P$ in
$\mathcal{G}^{\prime}$ from $w^{\prime}$ to $u$ that visits neither $x_{1}$
nor $x_{3}$. Recall that $w^{\prime}$ is only incident with the three edges
$\\{w^{\prime},w\\}$, $\\{w^{\prime},x_{1}\\}$, and $\\{w^{\prime},x_{3}\\}$
in $\mathcal{G}^{\prime}$. Since $P$ visits neither $x_{1}$ nor $x_{3}$, the
first edge traversed by $P$ is the edge $\\{w^{\prime},w\\}$ at a time step
strictly larger than $L$. By construction $\\{w^{\prime},w\\}$ is the only
edge incident with $w$ in $\mathcal{G}^{\prime}$ that exists in any time step
strictly larger than $L$, hence, $P$ cannot reach vertex $u$, since $u\neq w$.
A contradiction.

Concluding, $S$ contains only vertices of $V$.

Since no edge between any two vertices of $V$ was added while constructing
$\mathcal{G}^{\prime}$ from $\mathcal{G}$, each temporal path in
$\mathcal{G}^{\prime}$ that visits only vertices of $V$ is also a temporal
path in $\mathcal{G}$. Together with 9, this implies that $S$ is a closed tcc
in $\mathcal{G}$, which implies that $I$ is a yes-instance of Closed-TCC.

Recall that all versions of Closed-TCC are NP-hard [8, 13]. Moreover the
strict undirected version of Closed-TCC is W[1]-hard when parameterized by $k$
[8] and both directed versions of Closed-TCC are W[1]-hard when parameterized
by $k$ [13]. Together with Theorem 5.1, this implies the following
intractability results for Closed-TCC.

######  Theorem 5.3.

All versions of Closed-TCC are NP-hard even if
$\delta_{\mathrm{vd}}=\delta_{\mathrm{am}}=1$. More precisely, this hardness
holds on instances where the reachability graph is missing only a single arc
to be a complete bidirectional clique. Excluding the undirected non-strict
version of Closed-TCC, all versions of Closed-TCC are W[1]-hard when
parameterized by $k$ under these restrictions

##  6 Conclusion

We introduced two new parameters $\delta_{\mathrm{vd}}$ and
$\delta_{\mathrm{am}}$ that capture how far the reachability graph of a given
temporal graph is from being transitive. We demonstrated their applicability
when the goal is to find open tccs in a temporal graph, presenting FPT-
algorithms for each parameter individually, and a polynomial kernel with
respect to $\delta_{\mathrm{am}}$, assuming that the corresponding arc-
modification set of size $\delta_{\mathrm{am}}$ is given. Computing such a set
is NP-hard in general directed graphs [25]. An interesting question, also
formulated in that paper, is whether this parameter is at least approximable
to within a polynomial factor of $\delta_{\mathrm{am}}$. If so, our result
implies a polynomial kernel for Open-TCC when parameterized by
$\delta_{\mathrm{am}}$. Alternatively, the existence of a proper polynomial
kernel for Open-TCC when parameterized by $\delta_{\mathrm{am}}$ could also be
shown by finding an approximation for a minimum-size inherit transitivity
modulator due to Theorem 4.2 and the fact that the size of a minimum-size
inherit transitivity modulator never exceeds $2\cdot\delta_{\mathrm{am}}$.

Another natural question is to identify what are the other (temporal)
reachability problems for which our transitivity parameters could be useful.
For instance, consider a variant of the Open-TCC problem where we search for
_$d$ -tccs_, that is, tccs such that the fastest temporal path between the
vertices has duration at most $d$. It is plausible that our positive results
carry over to this version when applied to the  _$d$ -reachability graph_,
i.e., the graph whose arcs represent temporal paths of duration at most $d$.

Regarding Closed-TCC, our intractability results show that neither
$\delta_{\mathrm{vd}}$ nor $\delta_{\mathrm{am}}$ suffice to make this problem
tractable. However, our results do not preclude the existence of an FPT-
algorithm in the case that the arc modification operations are restricted to
deletion only, which remains to be investigated. Nonetheless, we still believe
that transitivity is a key aspect of the problem. The problem with Closed-TCC
is that the reachability graph itself does not encode whether the paths
responsible for reachability travel through internal or external vertices.

We would like to initiate the idea of considering further transitivity
parameters based on modifications of the temporal graph itself, not only of
the reachability graph. In particular, could FPT-algorithms for such
parameters be achieved for reachability problems such as Open-TCC with similar
performance as our FPT-algorithms for $\delta_{\mathrm{vd}}$ and
$\delta_{\mathrm{am}}$, and could these parameters make Closed-TCC tractable
as well? And if so, how difficult is the computation of such parameters?

## References

  * [1] Eleni C Akrida, Jurek Czyzowicz, Leszek Gasieniec, Łukasz Kuszner, and Paul G Spirakis.  Temporal flows in temporal networks.  Journal of Computer and System Sciences, 103:46–60, 2019.
  * [2] Eleni C Akrida, Leszek Gąsieniec, George B Mertzios, and Paul G Spirakis.  The complexity of optimal design of temporally connected graphs.  Theory of Computing Systems, 61:907–944, 2017.
  * [3] Eleni C Akrida, George B Mertzios, Paul G Spirakis, and Christoforos Raptopoulos.  The temporal explorer who returns to the base.  Journal of Computer and System Sciences, 120:179–193, 2021.
  * [4] Emmanuel Arrighi, Fedor V. Fomin, Petr A. Golovach, and Petra Wolf.  Kernelizing temporal exploration problems.  In Neeldhara Misra and Magnus Wahlström, editors, 18th International Symposium on Parameterized and Exact Computation, IPEC 2023, September 6-8, 2023, Amsterdam, The Netherlands, volume 285 of LIPIcs, pages 1:1–1:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023\.  URL: https://doi.org/10.4230/LIPIcs.IPEC.2023.1, doi:10.4230/LIPICS.IPEC.2023.1.
  * [5] Kyriakos Axiotis and Dimitris Fotakis.  On the size and the approximability of minimum temporally connected subgraphs.  In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016\.
  * [6] Sandeep Bhadra and Afonso Ferreira.  Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks.  In Ad-Hoc, Mobile, and Wireless Networks: Second International Conference, ADHOC-NOW2003, Montreal, Canada, October 8-10, 2003. Proceedings 2, pages 259–270. Springer, 2003.
  * [7] Benjamin Merlin Bumpus and Kitty Meeks.  Edge exploration of temporal graphs.  Algorithmica, 85(3):688–716, 2023.
  * [8] Arnaud Casteigts.  Finding structure in dynamic networks.  CoRR, abs/1807.07801, 2018.  URL: http://arxiv.org/abs/1807.07801, arXiv:1807.07801.
  * [9] Arnaud Casteigts and Timothée Corsini.  In search of the lost tree: Hardness and relaxation of spanning trees in temporal graphs.  In 31th Colloquium on Structural Information and Communication Complexity (SIROCCO), 2024.
  * [10] Arnaud Casteigts, Anne-Sophie Himmel, Hendrik Molter, and Philipp Zschoche.  Finding temporal paths under waiting time constraints.  Algorithmica, 83(9):2754–2802, 2021.
  * [11] Arnaud Casteigts, Michael Raskin, Malte Renken, and Viktor Zamaraev.  Sharp thresholds in random simple temporal graphs.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 319–326. IEEE Computer Society, 2022.
  * [12] Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, and Ge Xia.  Tight lower bounds for certain parameterized NP-hard problems.  Information and Computation, 201(2):216–231, 2005.
  * [13] Isnard Lopes Costa, Raul Lopes, Andrea Marino, and Ana Silva.  On Computing Large Temporal (Unilateral) Connected Components.  In Combinatorial Algorithms - 34th International Workshop, IWOCA 2023, Tainan, Taiwan, June 7-10, 2023, Proceedings, volume 13889 of Lecture Notes in Computer Science, pages 282–293. Springer, 2023.  doi:10.1007/978-3-031-34347-6\\_24.
  * [14] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, 2015.
  * [15] Rodney G. Downey and Michael R. Fellows.  Fundamentals of Parameterized Complexity.  Texts in Computer Science. Springer, 2013.
  * [16] Jessica Enright, Kitty Meeks, George B Mertzios, and Viktor Zamaraev.  Deleting edges to restrict the size of an epidemic in temporal networks.  In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.
  * [17] Thomas Erlebach and Jakob T Spooner.  Parameterized temporal exploration problems.  In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
  * [18] Till Fluschnik, Hendrik Molter, Rolf Niedermeier, Malte Renken, and Philipp Zschoche.  As time goes by: reflections on treewidth for temporal graphs.  In Treewidth, Kernels, and Algorithms: Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday, pages 49–77. Springer, 2020\.
  * [19] Till Fluschnik, Hendrik Molter, Rolf Niedermeier, Malte Renken, and Philipp Zschoche.  Temporal graph classes: A view through temporal separators.  Theoretical Computer Science, 806:197–218, 2020.
  * [20] Niels Grüttemeier and Christian Komusiewicz.  On the Relation of Strong Triadic Closure and Cluster Deletion.  Algorithmica, 82(4):853–880, 2020.
  * [21] David Kempe, Jon Kleinberg, and Amit Kumar.  Connectivity and inference problems for temporal networks.  In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 504–513, 2000.
  * [22] John M. Lewis and Mihalis Yannakakis.  The node-deletion problem for hereditary properties is np-complete.  Journal of Computer and System Sciences, 20(2):219–230, 1980.  doi:10.1016/0022-0000(80)90060-4.
  * [23] Jason Schoeters, Eric Sanlaville, Stefan Balev, and Yoann Pigné.  Temporally connected components.  Available at SSRN 4590651, 2024.
  * [24] Robert Endre Tarjan.  Depth-first search and linear graph algorithms.  SIAM Journal on Computing, 1(2):146–160, 1972.  doi:10.1137/0201010.
  * [25] Mathias Weller, Christian Komusiewicz, Rolf Niedermeier, and Johannes Uhlmann.  On making directed graphs transitive.  Journal of Computer and System Sciences, 78(2):559–574, 2012.  URL: https://doi.org/10.1016/j.jcss.2011.07.001, doi:10.1016/J.JCSS.2011.07.001.