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.
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 [
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 diference 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 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 ifrst 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 considering 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.
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]. where ,1 ≤ ,1 < ,2 ≤ ,2 < · · · intervals:
Given a set of pairwise disjoint intervals 1 = [,1, ,1], 2 = [,2, ,2], . . . , = [,, ,], < , ≤ ,, we can define the concatenation of these 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).
Input: A temporal graph = (, , ).
Output: An activity timeline of minimum span that covers .
1 2 3 4 = 1 = 2 = 3
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.
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,} ,1 − ,1 {′,0,} {,,}
{,′,} ,2 ,3 − ,2 {0,′0,} ,1 − ,3 {0,′0,} ,2
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 24 + 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, 24 + 2 + + 3 + 2] (4 timestamps) ,2 = [24 + 2 + + 3 + 3, 24 + 2 + + 3 + 3] (1 timestamp) Notice that ,1 and ,2 consists of a single timestamp. The time domain is the concatenation 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, } : = 24 + 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 1MinTimelineCover. 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 1MinTimelineCover. 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 ′ ⊆ 1-MinTimelineCover as follows: of , with | ′| = . We define a solution of • 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) + ( − )( + ).
Lemma 3. Given an instance of Vertex Cover, let be the corresponding instance of 1MinTimelineCover. 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.
Proof. It follows from Lemma 2 and Lemma 3, that we have designed a polynomial-time reduction from Vertex Cover to 1-MinTimelineCover. Since Vertex Cover is NP-hard [16], it follows that also 1-MinTimelineCover is NP-hard.
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 = [
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 , ,1 ,3 ,2 ,
, , , ,3
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 [
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 [
• 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.
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 timestamps and the local degree Δ ≤ 2.
Proof. By Lemma 4, Lemma 6 and Lemma 7 it follows that that we have designed a polynomialtime 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.
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 MinTimelineCover 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)ℎ| |).
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 parameterized 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. [9] A. Marino, A. Silva, Königsberg sightseeing: Eulerian walks in 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. 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 interactions 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.