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.