=Paper=
{{Paper
|id=Vol-3284/2973
|storemode=property
|title=Insights into the Complexity of Disentangling Temporal Graphs
|pdfUrl=https://ceur-ws.org/Vol-3284/2973.pdf
|volume=Vol-3284
|authors=Riccardo Dondi
|dblpUrl=https://dblp.org/rec/conf/ictcs/Dondi22
}}
==Insights into the Complexity of Disentangling Temporal Graphs==
<pdf width="1500px">https://ceur-ws.org/Vol-3284/2973.pdf</pdf>
<pre>
Insights into the Complexity of Disentangling
Temporal Graphs
Riccardo Dondi1
1
    Università degli Studi di Bergamo, Italy


                                         Abstract
                                         We consider a variant of vertex cover in temporal graphs recently introduced to summarize timeline
                                         activities in social networks. Since the problem is already NP-hard when the time domain considered
                                         consists of two timestamps, we analyse the complexity of the problem in other restricted cases. We
                                         prove that the problem is NP-hard when (1) there exists exactly one interaction in each timestamp and
                                         (2) when each vertex has at most two interactions in each timestamp and the time domain consists of
                                         three timestamps. Moreover, we prove that the problem is fixed parameter tractable when the parameter
                                         is the size of the time window activity, which bounds the number of vertices with active temporal edges
                                         in a timestamp and the length of the interval where a vertex has incident temporal edges.

                                         Keywords
                                         Temporal Graphs, Graph Algorithms, Computational Complexity, Vertex Cover




1. Introduction
The analysis of networks is recently considering representations that extend the classic graph
model. In this context, temporal graphs describe dynamics of edge activity in a discrete time
domain [1, 2]. Many works on temporal graphs have been focused on finding paths and analyzing
their connectivity [1, 3, 4, 5, 6, 7, 8, 9] and to find cohesive subgraphs [10, 11]. Recently, one of
the most prominent problem in graph theory and theoretical computer science, Vertex Cover,
has been considered also for temporal graphs [12, 13].
   In this paper we consider a variant of Vertex Cover, called Network Untangling, proposed
in [13] and motivated by discovering event timelines and summarizing temporal networks. Given
sequences of interactions, the problem looks for an explanation of the observed interactions
with few (and short) activity intervals, such that each interaction is covered by at least one of the
two entities involved (at least one of the two entities is active when the interaction is observed).
This can be seen as a variant of Vertex Cover, where we have to cover temporal edges with the
minimum activity of vertices, called span. The span of a vertex is the difference between the
starting and ending timestamps of the interval where it is defined to be active.
   Four formulations of the problem have been considered in [13], depending on the fact that
each vertex/entity can be active in one or 𝑘 ≥ 2 intervals and that the goal is to minimize the
sum of spans of vertex activities or the maximum activity span of a vertex. Here we focus on the


Proceedings of the 23rd Italian Conference on Theoretical Computer Science, Rome, Italy, September 7-9, 2022
" riccardo.dondi@unibg.it (R. Dondi)
                                       © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
    CEUR
    Workshop
    Proceedings
                  http://ceur-ws.org
                  ISSN 1613-0073
                                       CEUR Workshop Proceedings (CEUR-WS.org)
formulation where each vertex can be active in exactly one interval and the objective function is
the minimization of the sum of the span of vertex activities, a problem called MinTimelineCover.
   Other two variants of Vertex Cover in temporal graphs have been considered in [12]. A
first variant asks for the minimum number of vertex activities such that each non-temporal
edge 𝑒 = {𝑢, 𝑣} is temporally covered, that is there exists a timestamp 𝑡 where 𝑒 is active and
one of (𝑢, 𝑡) and (𝑣, 𝑡) belongs to the cover. A second variant asks each temporal edge to be
temporally covered at least once for every interval of a given length Δ. The two variants are
shown NP-hard, also in very restricted cases [12]. Further results on the problem variants,
including their approximability, have been given in [12, 14].
   The MinTimelineCover problem is known to be NP-hard also in very restricted cases, in
particular when the time domain consists of two timestamps [15] (notice that when the time
domain consists of a single timestamp, the problem is trivially in P, since any solution of the
problem has span 0). MinTimelineCover is fixed-parameter tractable, when parameterized by the
span of the solution and the time domain consists of exactly two timestamps [15]. Furthermore,
in [15] the parameterized complexity of the variants of Network Untangling proposed in [13]
has been explored, considering as parameters the number of vertices of the temporal graph, the
length of the time domain, the number of intervals of vertex activity and the span of a solution.
   In this paper, we further analyze the complexity of the MinTimelineCover problem by consid-
ering restrictions of the temporal input graph. We prove in Section 3 that the problem is NP-hard
even when there exists at most one interaction in each timestamp. In Section 4 we consider a
bound on the degree of the input temporal graph and on the length of the time domain and we
show that MinTimelineCover NP-hard when each vertex has at most two interactions in each
timestamp and the time domain consists of three timestamps. Finally, in Section 5 we prove
that the problem is fixed parameter tractable when the parameter is the size of the time window
activity that bounds (1) the number of vertices with temporal edges in a timestamp and (2) the
interval length where a vertex has incident temporal edges. We conclude the paper with some
open problems in Section 6. In Section 2 we present some definitions and we formally define
the MinTimelineCover problem. Some of the proofs are omitted due to space constraints.


2. Preliminaries
We start this section by introducing the definition of discrete time domain over which is defined
a temporal graph.

Definition 1. A discrete time domain 𝒯 is a sequence of timestamp 𝑡𝑖 , 1 ≤ 𝑖 ≤ |𝒯 |, where each
𝑡𝑖 is an integer and 𝑡𝑖 < 𝑡𝑖+1 . An interval 𝑇 = [𝑡𝑖 , 𝑡𝑗 ] over 𝒯 , where 𝑡𝑖 , 𝑡𝑗 ∈ 𝒯 and 𝑡𝑖 ≤ 𝑡𝑗 , is the
sequence of timestamps with value between 𝑡𝑖 and 𝑡𝑗 .

   Two intervals 𝑇1 = [𝑡𝑎,1 , 𝑡𝑏,1 ], 𝑇2 = [𝑡𝑎,2 , 𝑡𝑏,2 ] are disjoint if they do not share any timestamp,
that is 𝑡𝑎,1 ≤ 𝑡𝑏,1 < 𝑡𝑎,2 ≤ 𝑡𝑏,2 or 𝑡𝑎,2 ≤ 𝑡𝑏,2 < 𝑡𝑎,1 ≤ 𝑡𝑏,1 . The concatenation of the disjoint
intervals 𝑇1 and 𝑇2 is an interval 𝑇1 · 𝑇2 obtained by merging the two time intervals 𝑇1 and 𝑇2 ,
that is, assuming without loss of generality that 𝑡𝑎,1 ≤ 𝑡𝑏,1 < 𝑡𝑎,2 ≤ 𝑡𝑏,2 , it is defined as follows:

                                          𝑇1 · 𝑇2 = [𝑡𝑎,1 , 𝑡𝑏,2 ].
   Given a set of pairwise disjoint intervals 𝑇1 = [𝑡𝑎,1 , 𝑡𝑏,1 ], 𝑇2 = [𝑡𝑎,2 , 𝑡𝑏,2 ], . . . , 𝑇𝑞 = [𝑡𝑎,𝑞 , 𝑡𝑏,𝑞 ],
where 𝑡𝑎,1 ≤ 𝑡𝑏,1 < 𝑡𝑎,2 ≤ 𝑡𝑏,2 < · · · < 𝑡𝑎,𝑞 ≤ 𝑡𝑏,𝑞 , we can define the concatenation of these
intervals:
                                   𝑇1 · 𝑇2 · . . . 𝑇𝑞 = [𝑡𝑎,1 , 𝑡𝑞,2 ].
   We present now the definition of temporal graph. We consider a model where the vertex set
is not changing in the time domain.

Definition 2. A temporal graph 𝐺𝑡 = (𝑉𝑡 , 𝐸𝑡 , 𝒯 ) consists of

    1. A set 𝑉𝑡 of vertices
    2. A time domain 𝒯
    3. A set 𝐸𝑡 ⊆ 𝑉𝑡 × 𝑉𝑡 × 𝒯 of temporal edges, where a temporal edge of 𝐺𝑡 is a triple {𝑢, 𝑣, 𝑡},
       with 𝑢, 𝑣 ∈ 𝑉𝑡 and 𝑡 ∈ 𝒯 .

   Given an interval 𝐼 of 𝒯 , 𝐸𝑡 (𝐼) denotes the set of active edges in the timestamps of 𝐼, that is:

                               𝐸𝑡 (𝐼) = {{𝑢, 𝑣, 𝑡}|{𝑢, 𝑣, 𝑡} ∈ 𝐸𝑡 ∧ 𝑡 ∈ 𝐼}

𝐸𝑡 (𝑠) denotes the set of active edges in timestamp 𝑠.
   Given a vertex 𝑣 ∈ 𝑉𝑡 , an activity interval of 𝑣 is defined as an interval 𝐼𝑣 = [𝑙𝑣 , 𝑟𝑣 ] of the
time domain where 𝑣 is considered active, while in any timestamp not in 𝐼𝑣 , 𝑣 is considered
inactive. Informally, 𝐼𝑣 defines the time interval where 𝑣 is considered active. Notice that if
𝐼𝑣 = [𝑙𝑣 , 𝑟𝑣 ] is an activity interval of 𝑣, there may exist temporal edges {𝑢, 𝑣, 𝑡}, with 𝑡 < 𝑙𝑣 or
𝑡 > 𝑟𝑣 (see the example in Fig. 1). An activity timeline 𝒜 is a set of activity intervals, defined as:

                                              𝒜 = {𝐼𝑣 : 𝑣 ∈ 𝑉𝑡 }

Given a temporal graph 𝐺𝑡 = (𝑉𝑡 , 𝐸𝑡 , 𝒯 ), a timeline 𝒜 covers 𝐺𝑡 = (𝑉𝑡 , 𝐸𝑡 , 𝒯 ) if for each
temporal edge {𝑢, 𝑣, 𝑡} ∈ 𝐸𝑡 , 𝑡 belongs to 𝐼𝑢 or to 𝐼𝑣 , where 𝐼𝑢 (𝐼𝑣 , respectively) is the activity
interval of 𝑢 (of 𝑣, respectively) defined by 𝒜.
   The span of an interval 𝐼𝑣 = [𝑙𝑣 , 𝑟𝑣 ], for some 𝑣 ∈ 𝑉 , is defined as follows:

                                               𝑠(𝐼𝑣 ) = |𝑟𝑣 − 𝑙𝑣 |.

   Notice that for an interval 𝐼𝑣 = [𝑙𝑣 , 𝑟𝑣 ] consisting of a single timestamp, that is where 𝑙𝑣 = 𝑟𝑣 ,
it holds that 𝑠(𝐼𝑣 ) = 0. The overall span of an activity timeline 𝒜 is equal to
                                                        ∑︁
                                              𝑠(𝒜) =            𝑠(𝐼𝑣 ).
                                                        𝐼𝑣 ∈𝒜

   Now, we are ready to define the problem we are interested into (see the example of Fig. 1).

Problem 1. (MinTimelineCover)
Input: A temporal graph 𝐺𝑡 = (𝑉𝑡 , 𝒯 , 𝐸𝑡 ).
Output: An activity timeline of minimum span that covers 𝐺𝑡 .
    𝑣1



     𝑣2



     𝑣3



     𝑣4


                    𝑡=1                                  𝑡=2                                  𝑡=3
Figure 1: An example of MinTimelineCover on a temporal graph 𝐺𝑡 consisting of four vertices (𝑣1 ,
𝑣2 , 𝑣3 , 𝑣4 ) and three timestamps (1, 2, 3); for each timestamp, we present the active temporal edges
of 𝐺𝑡 . For example for 𝑡 = 1, the active edges are {𝑣1 , 𝑣3 , 1}, {𝑣1 , 𝑣4 , 1}, {𝑣2 , 𝑣3 , 1}. The intervals in
gray represent the activity intervals of each vertex; for example vertex 𝑣1 is active in timestamp 1, with
span equal to 0, vertex 𝑣2 is active in interval [1, 2] and it has a span equal to 1. Notice that the activity
timeline defined by the vertex activity intervals covers the temporal graph with total span equal to 1.


   Given a temporal graph 𝐺𝑡 = (𝑉𝑡 , 𝐸𝑡 , 𝒯 ) and a vertex 𝑣 ∈ 𝑉𝑡 , the local degree of 𝑣 in a
timestamp 𝑡, denoted by Δ𝐿 (𝑣, 𝑡), is the number of temporal edges {𝑣, 𝑢, 𝑡}, with 𝑢 ∈ 𝑉𝑡 . The
local degree Δ𝐿 of 𝐺𝑡 is the maximum over 𝑣 and 𝑡 of Δ𝐿 (𝑣, 𝑡).
   Given an interval 𝐼 of the time domain 𝒯 , the time window associated with 𝐼 (denoted by
𝑤(𝐼)) is defined as
                            𝑤(𝐼) = {(𝑣, 𝑡) : {𝑣, 𝑢, 𝑡} ∈ 𝐸𝑡 ∧ 𝑡 in 𝐼}
that is the set of pairs consisting of vertices of 𝑉𝑡 and timestamps of 𝐼, such that there exists a
temporal edge incident in 𝑣 in some timestamp of 𝐼. We define a temporal graph to be (𝑤, ℎ)-
window-constrained if (1) the temporal edges incident in each vertex belong to an interval of
length at most 𝑤 and (2) at most ℎ vertices are active in each timestamp.


3. Hardness of MinTimelineCover for Bounded Activity
In this section we consider the MinTimelineCover problem when each timestamp contains
at most a single active edge, and thus the local degree Δ𝐿 of 𝐺𝑇 is also bounded by 1. We
denote this restriction by 1-MinTimelineCover. We prove that 1-MinTimelineCover is NP-hard
by giving a reduction from the Vertex Cover problem. First, we recall the definition of Vertex
Cover:
    {𝑢𝑖 ,𝑢0 ,𝑡}     −        {𝑢′𝑖 ,𝑢0 ,𝑡}   {𝑢𝑖 ,𝑢𝑗 ,𝑡}   {𝑢𝑖 ,𝑢′𝑖 ,𝑡}    −     {𝑢0 ,𝑢′0 ,𝑡}    −     {𝑢0 ,𝑢′0 ,𝑡}


      𝐼𝑉,1         𝐼𝑆,1         𝐼𝑉,2           𝐼𝐸            𝐼𝑉,3        𝐼𝑆,2      𝐼𝐴,1        𝐼𝑆,3      𝐼𝐴,2

Figure 2: A sketch of the time domain 𝒯 built by the reduction. For each of the nine disjoint intervals
introduced to define 𝒯 , we report in the upper part a temporal edge defined in that interval; a symbol
− is used when no temporal edge is defined in the interval.


Problem 2. (Vertex Cover)
Input: A graph 𝐺 = (𝑉, 𝐸).
Output: A minimum cardinality vertex cover 𝑉 ′ of 𝐺 , that is for each {𝑢, 𝑣} ∈ 𝐸, 𝑢 ∈ 𝑉 ′ or
𝑣 ∈ 𝑉 ′.

   Given an instance 𝐺 = (𝑉, 𝐸) of Vertex Cover, where |𝑉 | = 𝑛 and |𝐸| = 𝑚, we build a
corresponding temporal graph 𝐺𝑡 = (𝑉𝑡 , 𝐸𝑡 , 𝒯 ), instance of 1-MinTimelineCover, as follows
(a sketch of the temporal graph is given in Fig. 2). First, we define the time domain 𝒯 , which
consists of 2𝑚4 + 𝑚2 + 𝑚 + 𝑛 + 3 timestamps and is defined starting from the following
disjoint intervals:

           𝐼𝑉,1 = [1, 𝑛] (𝑛 timestamps)                     𝐼𝑆,1 = [𝑛 + 1, 𝑚2 + 𝑛] (𝑚2 timestamps)



𝐼𝑉,2 = [𝑚2 +𝑛+1, 𝑚2 +2𝑛] (𝑛 timestamps) 𝐼𝐸 = [𝑚2 +2𝑛+1, 𝑚2 +𝑚+2𝑛] (𝑚 timestamps)


                     𝐼𝑉,3 = [𝑚2 + 𝑚 + 2𝑛 + 1, 𝑚2 + 𝑚 + 3𝑛] (𝑛 timestamps)
                  𝐼𝑆,2 = [𝑚2 + 𝑚 + 3𝑛 + 1, 𝑚4 + 𝑚2 + 𝑚 + 3𝑛] (𝑚4 timestamps)


             𝐼𝐴,1 = [𝑚4 + 𝑚2 + 𝑚 + 3𝑛 + 1, 𝑚4 + 𝑚2 + 𝑚 + 3𝑛 + 1] (1 timestamp)


         𝐼𝑆,3 = [𝑚4 + 𝑚2 + 𝑚 + 3𝑛 + 2, 2𝑚4 + 𝑚2 + 𝑚 + 3𝑛 + 2] (𝑚4 timestamps)


          𝐼𝐴,2 = [2𝑚4 + 𝑚2 + 𝑚 + 3𝑛 + 3, 2𝑚4 + 𝑚2 + 𝑚 + 3𝑛 + 3] (1 timestamp)
  Notice that 𝐼𝐴,1 and 𝐼𝐴,2 consists of a single timestamp. The time domain 𝒯 is the concate-
nation of the intervals defined previously:

                          𝒯 = 𝐼𝑉,1 · 𝐼𝑆,1 · 𝐼𝑉,2 · 𝐼𝐸 · 𝐼𝑉,3 · 𝐼𝑆,2 · 𝐼𝐴,1 · 𝐼𝑆,3 · 𝐼𝐴,2

  The set 𝑉𝑡 is defined as follows:

                            𝑉𝑡 = {𝑢𝑖 , 𝑢′𝑖 : 𝑣𝑖 ∈ 𝑉, 1 ≤ 𝑖 ≤ 𝑛} ∪ {𝑢0 } ∪ {𝑢′0 }
   Now, we define the set 𝐸𝑡 of temporal edges in each interval of the time domain 𝒯 . In each
time interval 𝐼𝑆,𝑥 , 𝑥 ∈ {1, 2, 3}, no temporal edge is active. Furthermore, we assume that the
edges of 𝐺 are ordered based on the lexicographic order, and we refer to the 𝑝-th edge of 𝐺 as
the edge in position 𝑝 based on this order. Recall that 𝐸𝑡 (𝐼) denotes the set of temporal edges
active in interval 𝐼. Next, we define the sets of temporal edges in 𝐼𝑉,1 , 𝐼𝑉,2 , 𝐼𝐸 , 𝐼𝑉,3 , 𝐼𝐴,1 and
𝐼𝐴,2 :

                               𝐸𝑡 (𝐼𝑉,1 ) = {{𝑢𝑖 , 𝑢0 , 𝑖} : 1 ≤ 𝑖 ≤ 𝑛}


                      𝐸𝑡 (𝐼𝑉,2 ) = {{𝑢′𝑖 , 𝑢0 , 𝑡} : 𝑡 = 𝑚2 + 𝑛 + 𝑖, 1 ≤ 𝑖 ≤ 𝑛}



     𝐸𝑡 (𝐼𝐸 ) = {{𝑢𝑖 , 𝑢𝑗 , 𝑡} : 𝑡 = 𝑚2 + 2𝑛 + 𝑝, 1 ≤ 𝑝 ≤ 𝑚, {𝑣𝑖 , 𝑣𝑗 } is the 𝑝-edges of 𝐸}


                  𝐸𝑡 (𝐼𝑉,3 ) = {{𝑢𝑖 , 𝑢′𝑖 , 𝑡} : 𝑡 = 𝑚2 + 𝑚 + 2𝑛 + 𝑖, 1 ≤ 𝑖 ≤ 𝑛}


                    𝐸𝑡 (𝐼𝐴,1 ) = {{𝑢0 , 𝑢′0 , 𝑡} : 𝑡 = 𝑚4 + 𝑚2 + 𝑚 + 3𝑛 + 1}


                   𝐸𝑡 (𝐼𝐴,2 ) = {{𝑢0 , 𝑢′0 , 𝑡} : 𝑡 = 2𝑚4 + 𝑚2 + 𝑚 + 3𝑛 + 3}.
  We start by proving some properties of 𝐺𝑡 . First, notice that by construction in each timestamp
there exists at most one active temporal edge, thus 𝐺𝑡 is an instance of 1-MinTimelineCover.
Now, we present a property of vertices 𝑢0 and 𝑢′0 .

Lemma 1. Given an instance 𝐺 of Vertex Cover, let 𝐺𝑡 be the corresponding instance of 1-
MinTimelineCover. Consider a solution 𝒜 of 1-MinTimelineCover on instance 𝐺𝑡 of span at most
𝑛(𝑚2 + 𝑚 + 2𝑛), then each of the vertices 𝑢0 and 𝑢′0 is active in exactly one of the timestamps of
intervals 𝐼𝐴,1 and 𝐼𝐴,2 .

  We show next how to relate a vertex cover of 𝐺 and a solution of MinTimelineCover on 𝐺𝑡 .

Lemma 2. Given an instance 𝐺 of Vertex Cover, let 𝐺𝑡 be the corresponding instance of 1-
MinTimelineCover. Given a vertex cover of 𝐺 consisting of 𝑘 vertices, there exists a solution of
1-MinTimelineCover on instance 𝐺𝑡 of span at most 𝑘(𝑚2 + 𝑚 + 2𝑛) + (𝑛 − 𝑘)(𝑛 + 𝑚).

Proof. Consider a vertex cover 𝑉 ′ ⊆ 𝑉 of 𝐺, with |𝑉 ′ | = 𝑘. We define a solution 𝒜 of
1-MinTimelineCover as follows:

    • Vertex 𝑢0 (𝑢′0 , respectively), is active in the unique timestamp of interval 𝐼𝐴,1 (of interval
      𝐼𝐴,2 , respectively); 𝑢0 and 𝑢′0 have a span equal to 0
    • For each vertex 𝑣𝑖 ∈ 𝑉 ∖ 𝑉 ′ , vertex 𝑢𝑖 is active in timestamp 𝑖 and has a span equal to 0,
      𝑢′𝑖 is active in the interval between timestamps 𝑚2 + 𝑛 + 𝑖 and 𝑚2 + 𝑚 + 2𝑛 + 𝑖, and
      has a span equal to 𝑚 + 𝑛.
    • For each vertex 𝑣𝑖 ∈ 𝑉 ′ , 𝑢𝑖 is active in the interval between timestamp 𝑖 and timestamp
      𝑚2 + 𝑚 + 2𝑛 + 𝑖, and has a span equal to 𝑚2 + 𝑚 + 2𝑛; vertex 𝑢′𝑖 is active in timestamp
      𝑚2 + 𝑛 + 𝑖 , and has a span equal to 0.

   First, we show that 𝒜 is a solution of 1-MinTimelineCover, that is it covers every temporal
edge of 𝐺𝑡 . Indeed, the temporal edges of 𝐼𝐴,1 and 𝐼𝐴,2 are covered by 𝑢0 and 𝑢′0 . The temporal
edges in 𝐼𝑉,1 are covered by vertices 𝑢𝑖 , 1 ≤ 𝑖 ≤ 𝑛, since 𝑢𝑖 is active in timestamp 𝑖. The
temporal edges of 𝐼𝑉,2 are covered by 𝑢′𝑖 , 1 ≤ 𝑖 ≤ 𝑛, since 𝑢′𝑖 is active in timestamp 𝑚2 + 𝑛 + 𝑖.
Since 𝑉 ′ is a vertex cover of 𝐺, by construction 𝑢𝑖 is active in interval [𝑖, 𝑚2 + 𝑚 + 𝑛 + 𝑖] or
𝑢𝑗 is active in interval [𝑗, 𝑚2 + 𝑚 + 2𝑛 + 𝑗]; both intervals include 𝐼𝐸 where temporal edge
{𝑢𝑖 , 𝑢𝑗 , 𝑡} is defined. Finally, the edges of 𝐼𝑉,3 are covered either by 𝑢𝑖 , if 𝑣𝑖 ∈ 𝑉 ′ , since 𝑢𝑖 in
this case is active in interval [𝑖, 𝑚2 + 𝑚 + 2𝑛 + 𝑖], or by 𝑢′𝑖 , if 𝑣𝑖 ∈ 𝑉 ∖ 𝑉 ′ , since 𝑢′𝑖 in this case
is active in interval [𝑚2 + 𝑛 + 𝑖, 𝑚2 + 𝑚 + 2𝑛 + 𝑖]. It follows that all the temporal edges are
covered, thus 𝒜 covers 𝐺𝑡 .
   Now, consider the span of 𝒜. Since 𝑘 vertices 𝑢𝑖 (with 𝑣𝑖 ∈ 𝑉 ′ ) have a span of 𝑚2 + 𝑚 + 2𝑛
and 𝑛 − 𝑘 vertices 𝑢′𝑖 (with 𝑣𝑖 ∈ 𝑉 ∖ 𝑉 ′ ) have a span of 𝑛 + 𝑚, the overall span of 𝒜 is
𝑘(𝑚2 + 𝑚 + 2𝑛) + (𝑛 − 𝑘)(𝑛 + 𝑚).


  Based on Lemma 1, we can prove the following result.

Lemma 3. Given an instance 𝐺 of Vertex Cover, let 𝐺𝑡 be the corresponding instance of 1-
MinTimelineCover. Given a solution 𝒜 of 1-MinTimelineCover on instance 𝐺𝑡 having span
𝑘(𝑚2 + 𝑚 + 2𝑛) + (𝑛 − 𝑘)(𝑛 + 𝑚), there exists a vertex cover of 𝐺 consisting of at most 𝑘 vertices.

  Now, we are able to prove the main result of this section.

Theorem 1. 1-MinTimelineCover is NP-hard.

Proof. It follows from Lemma 2 and Lemma 3, that we have designed a polynomial-time reduc-
tion from Vertex Cover to 1-MinTimelineCover. Since Vertex Cover is NP-hard [16], it follows
that also 1-MinTimelineCover is NP-hard.



4. MinTimelineCover for Bounded Degree and Time Domain
In this section we consider another restriction of the MinTimelineCover problem, when the
input temporal graph has bounded local degree and bounded time domain. We prove that
MinTimelineCover is NP-hard even when the time domain consists of three timestamps and the
local degree Δ𝐿 ≤ 2, by giving a reduction from Vertex Cover on cubic graphs (a variant of
Vertex Cover denoted by Cubic Vertex Cover). We recall that a graph is cubic when each of its
vertex has degree three.
   Given an instance 𝐺 = (𝑉, 𝐸) of Cubic Vertex Cover, we build a corresponding temporal
graph 𝐺𝑡 = (𝑉𝑡 , 𝐸𝑡 , 𝒯 ) as follows (a sketch of 𝐺𝑡 is given in Fig. 3). First, we define the time
domain 𝒯 = [1, 2, 3].
   The vertex set 𝑉𝑡 is defined as follows. Let 𝑈𝑖 , with 𝑣𝑖 ∈ 𝑉 and 1 ≤ 𝑖 ≤ |𝑉 |, be the following
set of vertices:

                            𝑈𝑖 = {𝑢𝑖,1 , 𝑢𝑖,2 , 𝑢𝑖,3 , 𝑤𝑖,𝑎 , 𝑤𝑖,𝑏 , 𝑧𝑖 : 𝑣𝑖 ∈ 𝑉 }.
  The set 𝑉𝑡 is then defined as follows:
                                                       |𝑉 |
                                                       ⋃︁
                                                𝑉𝑡 =          𝑈𝑖 .
                                                       𝑖=1

   The set 𝐸𝑡 consists of three subsets 𝐸𝑡,1 , 𝐸𝑡,2 , 𝐸𝑡,3 , representing edges active in timestamp
1, 2, 3, respectively. As in the reduction of Section 3, we assume that the edges of 𝐺 are ordered
based on lexicographic order. Since 𝐺 is cubic, based on this order we refer to the edges incident
on a vertex 𝑣 ∈ 𝑉 as the first (second, third, respectively) edge incident in 𝑣. The set 𝐸𝑡,1 , 𝐸𝑡,2 ,
𝐸𝑡,3 are defined as follows:

                            𝐸𝑡,1 = {{𝑤𝑖,𝑎 , 𝑧𝑖 , 1}, {𝑤𝑖,𝑏 , 𝑧𝑖 , 1} : 𝑣𝑖 ∈ 𝑉 }


         𝐸𝑡,2 = {{𝑢𝑖,1 , 𝑤𝑖,𝑎 , 2}, {𝑢𝑖,2 , 𝑤𝑖,𝑎 , 2}, {𝑢𝑖,2 , 𝑤𝑖,𝑏 , 2}, {𝑢𝑖,3 , 𝑤𝑖,𝑏 , 2} : 𝑣𝑖 ∈ 𝑉 }


                           𝐸𝑡,3 = {{𝑤𝑖,𝑎 , 𝑧𝑖 , 3}, {𝑤𝑖,𝑏 , 𝑧𝑖 , 3} : 𝑣𝑖 ∈ 𝑉 } ∪
                {{𝑢𝑖,𝑥 , 𝑢𝑗,𝑦 , 3} : {𝑣𝑖 , 𝑣𝑗 } ∈ 𝐸 and {𝑣𝑖 , 𝑣𝑗 } is the 𝑥-th edge of 𝑣𝑖
                                and the 𝑦-th edge of 𝑣𝑗 1 ≤ 𝑥, 𝑦 ≤ 3}
  We start by proving some properties of the temporal graph 𝐺𝑡 .

Lemma 4. Given an instance 𝐺 of Cubic Vertex Cover, let 𝐺𝑡 be the corresponding instance of
MinTimelineCover. Then the local degree Δ𝐿 of 𝐺𝑇 is 2.

   Next, we prove that we can restrict ourselves to solutions where each vertex 𝑧𝑖 , 1 ≤ 𝑖 ≤ |𝑉 |,
is active only in timestamp 3.

Lemma 5. Given an instance 𝐺 of Cubic Vertex Cover, let 𝐺𝑡 be the corresponding instance
of MinTimelineCover. Then, given a solution 𝒜 of MinTimelineCover on instance 𝐺𝑡 , we can
compute in polynomial time a solution 𝒜′ of MinTimelineCover on instance 𝐺𝑡 such that each
vertex 𝑧𝑖 is active only in timestamp 3 and the span of 𝒜′ is at most the span of 𝒜.

  Now, we show how to relate and a solution of MinTimelineCover on 𝐺𝑡 .

Lemma 6. Given an instance 𝐺 of Cubic Vertex Cover, let 𝐺𝑡 be the corresponding instance of
MinTimelineCover. Then, given a solution 𝑉 ′ of Cubic Vertex Cover, with |𝑉 ′ | = 𝑘, we can
compute in polynomial time a solution of MinTimelineCover on instance 𝐺𝑡 of span at most
|𝐸| + 𝑘 − |𝑉 |.
                                                          𝑢𝑖,1                                   𝑤𝑖,𝑎


              𝑤𝑖,𝑎                               𝑤𝑖,𝑎
                                                                                           𝑧𝑖

                                                 𝑢𝑖,2
        𝑧𝑖
                                                                                                  𝑤𝑖,𝑏

                                                 𝑤𝑖,𝑏
              𝑤𝑖,𝑏

                                                          𝑢𝑖,3                            𝑢𝑖,𝑥           𝑢𝑗,𝑦




             𝐸𝑡,1                                         𝐸𝑡,2                                   𝐸𝑡,3
Figure 3: The structure of the temporal graph 𝐺𝑡 ; 𝐸𝑡,1 , 𝐸𝑡,2 , 𝐸𝑡,3 are the sets of temporal edges defined
in the three timestamps 1, 2 and 3, respectively.


Proof. Consider a solution 𝑉 ′ of Cubic Vertex Cover on instance 𝐺, we define a solution 𝒜 of
MinTimelineCover on instance 𝐺𝑡 as follows. For each set 𝑈𝑖 , 1 ≤ 𝑖 ≤ |𝑉 |, associated with
𝑣𝑖 ∈ 𝑉 ∖ 𝑉 ′ , 𝒜 is defined as follows:

    • 𝑤𝑖,𝑎 , 𝑤𝑖,𝑏 are active in interval [1, 2], each one with span 1
    • For each {𝑣𝑖 , 𝑣𝑗 } ∈ 𝐸, which is the 𝑝-th edge of 𝑣𝑖 and the 𝑞-th edge of 𝑣𝑗 , 𝑢𝑖,𝑝 is active
      in timestamp 3 with span 0
    • Vertex 𝑧𝑖 is active in timestamp 3, with span 0.

  For each set 𝑈𝑖 , 1 ≤ 𝑖 ≤ |𝑉 |, associated with 𝑣𝑖 ∈ 𝑉 ′ , 𝒜 is defined as follows:

    • Vertices 𝑤𝑖,𝑎 , 𝑤𝑖,𝑏 are active in timestamp 1, each one with span 0
    • Each vertex 𝑢𝑖,𝑝 , 1 ≤ 𝑝 ≤ 3, is active in timestamp 2 (the span of 𝑢𝑖 depends on the next
      point)
    • For each {𝑣𝑖 , 𝑣𝑗 } ∈ 𝐸, with 𝑣𝑖 , 𝑣𝑗 ∈ 𝑉 ′ , which is the 𝑝-th edge of 𝑣𝑖 and the 𝑞-th edge of
      𝑣𝑗 : if 𝑖 < 𝑗 then 𝑢𝑖,𝑝 is active in interval [2, 3] (with span 1), else 𝑢𝑗,𝑞 is active in interval
      [2, 3] (with span 1).
    • Vertex 𝑧𝑖 is active in timestamp 3.

  By construction, 𝒜 covers each temporal edge of 𝐺𝑡 . Indeed, the temporal edges in 𝐸𝑡,1 are
covered by 𝑤𝑖,𝑎 , 𝑤𝑖,𝑏 for each 𝑖 with 1 ≤ 𝑖 ≤ |𝑉 |. The temporal edges in 𝐸𝑡,2 are either covered
by 𝑤𝑖,𝑎 , 𝑤𝑖,𝑏 , if 𝑣𝑖 ∈ 𝑉 ∖ 𝑉 ′ , or by 𝑢𝑖,1 , 𝑢𝑖,2 , 𝑢𝑖,3 , if 𝑣𝑖 ∈ 𝑉 ′ . The temporal edges {𝑤𝑖,𝑎 , 𝑧𝑖 , 3}
and {𝑤𝑖,𝑏 , 𝑧𝑖 , 3} of 𝐸𝑡,3 are covered by 𝑧𝑖 ; the temporal edges {𝑢𝑖,𝑥 , 𝑢𝑗,𝑦 , 3} are covered by one
of 𝑢𝑖,𝑥 , 𝑢𝑗,𝑦 .
   Now, the span of 𝒜 is 1 for each {𝑣𝑖 , 𝑣𝑗 } ∈ 𝐸, where 𝑣𝑖 , 𝑣𝑗 ∈ 𝑉 ′ . Consider now an edge
{𝑣𝑖 , 𝑣𝑗 } ∈ 𝐸, where either 𝑣𝑖 or 𝑣𝑗 in 𝑉 ∖ 𝑉 ′ , assume without loss of generality that 𝑣𝑖 ∈ 𝑉 ′ ;
then 𝒜 has a span of 2 for the set 𝑈𝑖 (both 𝑤𝑖,𝑎 and 𝑤𝑖,𝑏 have a span 1) for the three edges
incident in 𝑣𝑖 in 𝐺. Hence the overall span of 𝒜 is |𝐸| − |𝑉 ∖ 𝑉 ′ | = |𝐸| + 𝑘 − |𝑉 |, thus
concluding the proof.


  Based on Lemma 5, we can prove the following result.
Lemma 7. Given an instance 𝐺 of Cubic Vertex Cover let 𝐺𝑡 be the corresponding instance of
MinTimelineCover. Then, given a solution MinTimelineCover on instance 𝐺𝑡 of span |𝐸|+𝑘−|𝑉 |,
we can compute in polynomial time a solution of Cubic Vertex Cover of size at most 𝑘.
  Now, we can prove the main result of this section.
Theorem 2. MinTimelineCover is NP-hard even when the time domain consists of three times-
tamps and the local degree Δ𝐿 ≤ 2.
Proof. By Lemma 4, Lemma 6 and Lemma 7 it follows that that we have designed a polynomial-
time reduction from Cubic Vertex Cover to MinTimelineCover when the time domain consists
of three timestamps and the local degree Δ𝐿 ≤ 2. Since Cubic Vertex Cover is NP-hard [17],
it follows that also MinTimelineCover is NP-hard when the time domain consists of three
timestamps and the local degree Δ𝐿 ≤ 2.



5. Bounding the Time Window
In this section we consider the parameterized complexity of MinTimelineCover for (𝑤, ℎ)-
window constrained temporal graphs, when the parameters are 𝑤, ℎ (the size of the time
window). Notice that when one of 𝑤, ℎ is the parameter, the problem is not in the class XP (if
ℎ = 2 for the result in Section 3, if 𝑤 = 2 for the hardness of MinTimelineCover on a time
domain of two timestamps [15]).
   We define 𝑊𝑗,𝑤 = 𝑤([𝑗 − 𝑤 + 1, 𝑗]), that is a time window of length 𝑤 that ends in timestamp
𝑗 and that consists of the set of pairs (𝑣, 𝑡) such that 𝑣 has an active edge in timestamp 𝑡, with
𝑗 − 𝑤 + 1 ≤ 𝑡 ≤ 𝑗.
   An activity assignment 𝐹𝑗,𝑤 for a time window 𝑊𝑗,𝑤 is a function that establishes, for each
pair (𝑣, 𝑡) of 𝑊𝑗,𝑤 , if 𝑣 is active in timestamp 𝑡. Formally, an activity assignment 𝐹𝑗,𝑤 is a
function
                                       𝐹𝑗,𝑤 : 𝑊𝑗,𝑤 → {0, 1}
such that for each pair (𝑣, 𝑡) it holds that:
    • 𝑣 is active in timestamp 𝑡 if and only if 𝐹𝑗,𝑤 (𝑣, 𝑡) = 1 (thus 𝑣 is not active in timestamp 𝑡
      if and only if 𝐹𝑗,𝑤 (𝑣, 𝑡) = 0)
    • if 𝐹𝑗,𝑤 (𝑣, 𝑡1 ) = 1 and 𝐹𝑗,𝑤 (𝑣, 𝑡2 ) = 1, with 𝑗 − 𝑤 + 1 ≤ 𝑡1 ≤ 𝑡2 ≤ 𝑗, then 𝐹𝑗,𝑤 (𝑣, 𝑡) = 1
      for each 𝑡 with 𝑡1 ≤ 𝑡 ≤ 𝑡2 .
   The span of 𝐹𝑗,𝑤 , denoted by 𝑠(𝐹𝑗,𝑤 ), is the span induced by the activity assignment 𝐹𝑗,𝑤 .
   Consider two time windows 𝑊𝑗,𝑤 and 𝑊𝑖,𝑤 , with 1 ≤ 𝑗 − 𝑤 + 1 ≤ 𝑖 < 𝑗 ≤ |𝒯 |, and
two assignment functions 𝐹𝑗,𝑤 and 𝐹𝑖,𝑤 . 𝐹𝑗,𝑤 and 𝐹𝑖,𝑤 are in agreement if, for each (𝑣, 𝑡) ∈
𝑊𝑗,𝑤 ∩ 𝑊𝑖,𝑤 it holds that 𝐹𝑗,𝑤 (𝑣, 𝑡) = 𝐹𝑖,𝑤 (𝑣, 𝑡). An activity timeline 𝒜 is in agreement with
an activity assignment 𝐹𝑗,𝑤 if the activity defined by 𝒜 for the pairs in 𝑊𝑗,𝑤 is identical to 𝐹𝑗,𝑤 .
   Next, we describe a dynamic programming algorithm to compute a solution of MinTime-
lineCover parameterized by 𝑤 and ℎ. Given two assignment functions 𝐹𝑗,𝑤 and 𝐹𝑗−1,𝑤 that
are in agreement, define the value 𝐷(𝐹𝑗,𝑤 , 𝐹𝑗−1,𝑤 ) as the span added by 𝐹𝑗,𝑤 (in timestamp 𝑗)
with respect to 𝐹𝑗−1,𝑤 . Formally, 𝐷(𝐹𝑗,𝑤 , 𝐹𝑗−1,𝑤 ) is defined as follows:


𝐷(𝐹𝑗,𝑤 , 𝐹𝑗−1,𝑤 ) = |{𝑣 : (𝑣, 𝑗 −1) ∈ 𝑊𝑗−1,𝑤 ∧(𝑣, 𝑗) ∈ 𝑊𝑗,𝑤 ∧𝐹𝑗,𝑤 (𝑣, 𝑗) = 𝐹𝑗−1,𝑤 (𝑣, 𝑗) = 1}|

  Given an activity assignment 𝐹𝑗,𝑤 of an active window 𝑊𝑗,𝑤 , define the function 𝐶[𝐹𝑗,𝑤 ] as
the minimum span of an activity timeline of the temporal graph 𝐺𝑡 on interval [1, 𝑗], such that:

   1. The activity of vertices in the time window 𝑊𝑗,𝑤 is defined by 𝐹𝑗,𝑤
   2. Each temporal edge {𝑢, 𝑣, 𝑡} of 𝐺𝑡 , with 1 ≤ 𝑡 ≤ 𝑗, is covered
   3. Each vertex active in timestamp 𝑗 is not active in interval [1, 𝑗 − 𝑤] (since 𝐺𝑡 is (𝑤, ℎ)-
      window constrained)

  Now, 𝐶[𝐹𝑗,𝑤 ] is computed with the following recurrence:

    • If 𝑗 > 𝑤, then 𝐶[𝐹𝑗,𝑤 ] is the minimum, over 𝐹𝑗−1,𝑤 in agreement with 𝐹𝑗,𝑤 , of

                                     𝐶[𝐹𝑗−1,𝑤 ] + 𝐷(𝐹𝑗,𝑤 , 𝐹𝑗−1,𝑤 )

    • If 𝑗 = 𝑤, 𝐶[𝐹𝑤,𝑤 ] = 𝑠(𝐹𝑤,𝑤 ), that is the span of 𝐹𝑤,𝑤 .

  Next, we show the correctness of the recurrence.
Lemma 8. 𝐶[𝐹𝑗,𝑤 ] = 𝑞, if and only if there exists an activity timeline of 𝐺𝑡 in interval [1, 𝑗] of
span 𝑞.
  Based on Lemma 8, we can prove the main result of this section.
Theorem 3. A solution of MinTimelineCover on instance 𝐺𝑡 can be computed in 𝑂(2ℎ(𝑤+1) ℎ|𝒯 |)
time.
Proof. The correctness of the recurrence follows from Lemma 8, thus the span of an optimal
solution of MinTimelineCover on instance 𝐺𝑡 is computed in entry 𝐶[𝐹|𝒯 |,𝑤 ].
  Next, we consider the time complexity of the algorithm. The base case 𝐶[𝐹𝑤,𝑤 ] can be
computed in 𝑂(2ℎ𝑤 ) time, as there exist at most ℎ vertices with active temporal edges in
each timestamp of interval [1, 𝑤]. Now, we consider the case 𝑗 > 𝑤. First, notice that each
entry 𝐶[𝐹𝑗,𝑤 ] can have at most 2ℎ𝑤 values and there are 𝑂(𝒯 ) of such entries. Now, 𝐶[𝐹𝑗,𝑤 ]
is computed starting from the values 𝐶[𝐹𝑗−1,𝑤 ] (where 𝐹𝑗,𝑤 and 𝐹𝑗−1,𝑤 are in agreement)
This requires the definition of the activity timeline of vertices active in timestamp 𝑗 (at most
ℎ), in 𝑂(2ℎ ) time and, for each of them, the computation of 𝐷(𝐹𝑗,𝑤 , 𝐹𝑗−1,𝑤 ), which requires
𝑂(ℎ) time. Hence the overall time complexity of the dynamic programming algorithm is
𝑂(2ℎ(𝑤+1) ℎ|𝒯 |).



6. Conclusion
We have considered a variant of Vertex Cover, called MinTimelineCover, on temporal graphs.
We have shown that the problem is NP-hard even in restricted cases (one temporal edge active
in each timestamp, local degree two for temporal graphs on a time domain of three timestamps).
Moreover, we have shown that MinTimelineCover is fixed-parameter tractable when the size of
the activity time window is the parameter.
   There are several interesting future directions related to MinTimelineCover. First, the param-
eterized complexity of MinTimelineCover is open when the problem is parameterized by the
span of the solution (recall that in this case the problem is fixed-parameter tractable when the
time domain consists of two timestamps [15]). Moreover, it would be interesting to analyze the
approximation complexity of the problem.


References
 [1] D. Kempe, J. M. Kleinberg, A. Kumar, Connectivity and inference problems for temporal
     networks, J. Comput. Syst. Sci. 64 (2002) 820–842. doi:10.1006/jcss.2002.1829.
 [2] P. Holme, Modern temporal network theory: a colloquium, The European Physical Journal
     B 88 (2015) 234.
 [3] H. Wu, J. Cheng, S. Huang, Y. Ke, Y. Lu, Y. Xu, Path problems in temporal graphs, Proc.
     VLDB Endow. 7 (2014) 721–732. doi:10.14778/2732939.2732945.
 [4] H. Wu, J. Cheng, Y. Ke, S. Huang, Y. Huang, H. Wu, Efficient algorithms for temporal path
     computation, IEEE Trans. Knowl. Data Eng. 28 (2016) 2927–2942. doi:10.1109/TKDE.
     2016.2594065.
 [5] T. Erlebach, M. Hoffmann, F. Kammer, On temporal graph exploration, J. Comput. Syst.
     Sci. 119 (2021) 1–18. doi:10.1016/j.jcss.2021.01.005.
 [6] P. Zschoche, T. Fluschnik, H. Molter, R. Niedermeier, The complexity of finding small
     separators in temporal graphs, J. Comput. Syst. Sci. 107 (2020) 72–92. doi:10.1016/j.
     jcss.2019.07.006.
 [7] T. Fluschnik, H. Molter, R. Niedermeier, M. Renken, P. Zschoche, Temporal graph classes:
     A view through temporal separators, Theor. Comput. Sci. 806 (2020) 197–218. doi:10.
     1016/j.tcs.2019.03.031.
 [8] B. M. Bumpus, K. Meeks, Edge exploration of temporal graphs, in: P. Flocchini, L. Moura
     (Eds.), Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Ottawa,
     ON, Canada, July 5-7, 2021, Proceedings, volume 12757 of Lecture Notes in Computer Science,
     Springer, 2021, pp. 107–121. doi:10.1007/978-3-030-79987-8\_8.
 [9] A. Marino, A. Silva, Königsberg sightseeing: Eulerian walks in temporal graphs, in: P. Floc-
     chini, L. Moura (Eds.), Combinatorial Algorithms - 32nd International Workshop, IWOCA
     2021, Ottawa, ON, Canada, July 5-7, 2021, Proceedings, volume 12757 of Lecture Notes in
     Computer Science, Springer, 2021, pp. 485–500. doi:10.1007/978-3-030-79987-8\_34.
[10] P. Rozenshtein, F. Bonchi, A. Gionis, M. Sozio, N. Tatti, Finding events in temporal
     networks: segmentation meets densest subgraph discovery, Knowl. Inf. Syst. 62 (2020)
     1611–1639. doi:10.1007/s10115-019-01403-9.
[11] R. Dondi, M. M. Hosseinzadeh, Dense sub-networks discovery in temporal networks, SN
     Comput. Sci. 2 (2021) 158. doi:10.1007/s42979-021-00593-w.
[12] E. C. Akrida, G. B. Mertzios, P. G. Spirakis, C. L. Raptopoulos, The temporal explorer who
     returns to the base, J. Comput. Syst. Sci. 120 (2021) 179–193. doi:10.1016/j.jcss.2021.
     04.001.
[13] P. Rozenshtein, N. Tatti, A. Gionis, The network-untangling problem: from interac-
     tions to activity timelines, Data Min. Knowl. Discov. 35 (2021) 213–247. doi:10.1007/
     s10618-020-00717-5.
[14] T. Hamm, N. Klobas, G. B. Mertzios, P. G. Spirakis, The complexity of temporal vertex
     cover in small-degree graphs, CoRR abs/2204.04832 (2022). doi:10.48550/arXiv.2204.
     04832.
[15] V. Froese, P. Kunz, P. Zschoche, Disentangling the computational complexity of network
     untangling, in: L. D. Raedt (Ed.), Proceedings of the Thirty-First International Joint
     Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, ijcai.org,
     2022, pp. 2037–2043. doi:10.24963/ijcai.2022/283.
[16] R. M. Karp, Reducibility among combinatorial problems, in: R. E. Miller, J. W. Thatcher
     (Eds.), Proceedings of a symposium on the Complexity of Computer Computations, held
     March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New
     York., The IBM Research Symposia Series, Plenum Press, New York, 1972, pp. 85–103.
[17] P. Alimonti, V. Kann, Some APX-completeness results for cubic graphs, Theor. Comput.
     Sci. 237 (2000) 123–134.

</pre>