Disentangling the Computational Complexity of Network Untangling

1 Introduction

The classical VERTEX COVER problem is among the most well-studied NP-hard problems on static graphs especially in the context of parameterized algorithmics. In fact, it is often referred to as the Drosophila of parameterized complexity [Downey and Fellows, 2013; Fellows et al., 2018]. Real-world graphs, however, are often dynamic and change over time. In modern applications, this temporal information is readily available and allows for more realistic models. This leads algorithmic research to focus on temporal graphs [Boehmer et al., 2021; Bumpus and Meeks, 2021; Deligkas and Potapov, 2020; Erlebach et al., 2021; Fan et al., 2021; Holme and Saram¨aki, 2012; Michail and Spirakis, 2016; Singer et al., 2019]. In a temporal graph, edges can appear and disappear over time, which is formalized by a sequence E1, . . . , Eτ of edge sets over a fixed set V of vertices, where τ ≥ 1 denotes the lifetime of the temporal graph. Several classical graph problems have been studied on temporal graphs [Akrida et al., 2020; Casteigts et al., 2021; Klobas et al., 2021; Mertzios et al., 2020; Mertzios et al., 2021; Zschoche et al., 2020].

In this paper, we study the network untangling problem introduced by Rozenshtein et al. [2017; 2021], which is a temporal variant of VERTEX COVER and motivated by data mining applications such as discovering event timelines and summarizing temporal networks. Here, edges in the temporal graph model certain interactions between entities (vertices). The goal is to explain the observed interactions by selecting few (and short) activity intervals for each entity such that at the time of an interaction at least one of the two entities is active. The formal definition is as follows: Let G = (V, (Ei)i∈[τ]) be a temporal graph. A k-activity timeline is a set T containing at most k time intervals for each vertex, that is, T ⊆ {(v, a, b) ∈ V × [τ] × [τ] | a ≤ b} such that |{(v, a, b) ∈ T }| ≤ k for each v ∈ V . We say that T covers G if for each t ∈ [τ] and each {u, v} ∈ Et, T contains some (u, a, b) with t ∈ [a, b] or some (v, a, b) with t ∈ [a, b]. That is, for each time step t, the set {v ∈ V | (v, a, b) ∈ T , t ∈ [a, b]} must be a vertex cover for the graph Gt = (V,Et). The task is to find a k-activity timeline that minimizes some objective regarding the interval lengths. Rozenshtein et al. [2021] introduced the following two problems.

MINTIMELINE∞

Input: A temporal graph G = (V,E1, . . . ,Eτ) and k, ℓ ∈ N0.

Question: Is there a k-activity timeline T covering G such that max(v,a,b)∈T (b - a) ≤ ℓ?

MINTIMELINE+

Input: A temporal graph G = (V,E1, . . . ,Eτ) and k, ℓ ∈ N0.

Question: Is there a k-activity timeline T covering G such that ∑(v,a,b)∈T (b - a) ≤ ℓ?

An example instance and solutions for each of these two problems are pictured in Figure 1. Note that both problems are equivalent if ℓ = 0.

Rozenshtein et al. [2021] showed that both problems are NP-hard and hard to approximate in polynomial time. They focus on developing heuristics and show in a case study that activity timelines can successfully be recovered for realworld data of Twitter users. In this work, we provide a deeper complexity-theoretic understanding of both problems through the lens of parameterized complexity theory. To this end, we study the influence of several natural problem parameters on the algorithmic complexity, namely, the number n of vertices, the lifetime τ , the maximum number k of intervals per vertex, and the interval length bound ℓ. In our multivariate analysis, we identify for both problems which parameter combinations yield fixed-parameter tractability and which combinations are intractable. In doing so, we reveal interesting connections to seemingly unrelated problems like graph coloring and bin packing. Our results yield an (almost) tight characterization and pave the way for a comprehensive picture of the computational complexity landscape of network untangling.

Related Work. As the literature on edge covering is extremely rich, we only consider studies closely related to our setting. For a broader overview on the topic of temporal network mining, we refer to a recent tutorial [Rozenshtein and Gionis, 2019]. Our main reference is the work by Rozenshtein et al. [2021] who introduced both problems and showed that MINTIMELINE∞ is polynomial-time solvable for k = 1, whereas MINTIMELINE+ is NP-hard for k = 1. Moreover, they showed that both problems are NP-hard for ℓ = 0 with unbounded k and thus not approximable in polynomial time. They develop efficient heuristics to solve the problems and provide experiments to evaluate the performance of their approaches.

Akrida et al. [2020] studied a different variant of VERTEX COVER on temporal graphs. Their model expects an edge to be covered at least once over every time window of some given size ∆. That is, they define a temporal vertex cover as a set S ⊆ V × [τ] such that, for every time window of size ∆ and for each edge e = {v,w} appearing in a time step contained in the time window, it holds that (v, t) ∈ S or (w, t) ∈ S for some t in the time window with timeedge (e, t). Among other results, they provide NP-hardness results in very restricted settings.

Fluschnik et al. [2019] and Heeger et al. [2021] studied the parameterized complexity of a "multistage" variant of VERTEX COVER. Here, one is given a temporal graph and seeks a sequence of vertex covers of size at most k (one for each layer of the temporal graph) such that consecutive vertex covers are in some sense similar, e.g., the symmetric difference of two consecutive vertex covers is upper-bounded by some value [Fluschnik et al., 2019] or the sum of symmetric differences of all consecutive vertex covers is upper-bounded by some value [Heeger et al., 2021].

Our Contributions. We almost completely settle the parameterized complexity of MINTIMELINE∞ and MINTIMELINE+ for all combinations of the parameters n, τ, k, and ℓ. Table 1 gives an overview of the central results. It turns out that both problems are already NP-hard if the temporal graph contains three identical layers and k = 2 and ℓ = 0 (Corollary 3). This strengthens the hardness result by Rozenshtein et al. [2021] for ℓ = 0 and implies that fixed-parameter tractability can only be achieved in combination with the parameter n. Interestingly, the two problems behave somewhat differently here. Our two main results state that MINTIMELINE∞ parameterized by n is W[1]-hard even for ℓ = 1 (Theorem 11), while MINTIMELINE+ parameterized by n + ℓ is in FPT (Theorem 8). We further show that both problems are in XP when parameterized by n (Theorem 6) and in FPT if ℓ = 0 (Lemma 9). Theorem 6 shows that MINTIMELINE+ is also in FPT for n + k and Theorem 7 shows the same for MINTIMELINE∞. As regards the case k = 1, we strengthen the NP-hardness of MINTIMELINE+ showing that it already holds for two layers (Theorem 5). Note that n + τ trivially yields fixed-parameter tractability since the instance size is bounded in these numbers. Thus, for MINTIMELINE∞, we obtain a full complexity dichotomy. For MINTIMELINE+, the parameterized complexity regarding n remains open. Notably, our hardness results also imply running time lower bounds based on the Exponential Time Hypothesis 1 (ETH) (Corollaries 4 and 14).

Due to space constraints, several proofs (marked by ⋆) are deferred to the full version of this paper. 2

2 Preliminaries

We denote the positive integers by N and let N0 := N ∪ {0}. For n ∈ N, let [n] := {1, . . . , n}.

If not specified otherwise, a graph is static and undirected. We refer to Diestel [2016] for details on notation in graph theory. If G = (V,E) is a graph and S ⊆ V , let inc(S) := {e ∈ E | e ∩ S ̸= ∅} denote the set of edges incident to at least one vertex in S. A temporal graph G := (V, (Ei)τi=1 ) consists of a finite vertex set V and a sequence of edge sets E1, . . . ,Eτ ⊆ (V2 ). The pair (e, i) is a time-edge of G if e ∈ Ei. The graph (V,Ei) is called the i-th layer of G. The size of G := (V, (Ei)τi=1 ) is |G| := |V |+∑τt=1 max{1, |Et|}. Let Σ denote a finite alphabet. A parameterized problem L ⊆ {(x, k) ∈ Σ∗ ×N0} is a subset of all instances (x, k) in Σ∗ ×N0, where k denotes the parameter. A parameterized problem L is (i) fixed-parameter tractable (or contained in the class FPT) if there is an algorithm that decides every instance (x, k) for L in f(k) · |x|O(1) time, (ii) contained in the class XP if there is an algorithm that decides every instance (x, k) for L in |x|f(k) time, and (iii) para-NP-hard if L is NP-hard for some constant value of the parameter, where f is any computable function that only depends on the parameter. Note that FPT ⊆ XP. If a parameterized problem is W[1]-hard, then it is presumably not in FPT, and if it is paraNP-hard, then it is not in XP (unless P = NP). Further details can be found in [Downey and Fellows, 2013].

1 The Exponential Time Hypothesis [Impagliazzo and Paturi, 2001] states that 3-SAT cannot be solved in O(2cn ) time for some constant c > 0, where n is the number of variables of the input formula.

2 On the arXiv: https://arxiv.org/abs/2204.02668.

3 First Results

This section sets the basis of our parameterized complexity analysis containing results for most of the parameter combinations (except for n + ℓ).

We start with the general observation (which we will use later) that, for ℓ = 0, the temporal order of the layers is irrelevant since every element in a k-activity timeline covers only edges of one layer.

Observation 1. Let π: [τ] → [τ] be a permutation. Then, the instance ((V, (Ei)i∈[τ]), k, 0) is a yes-instance of MINTIMELINE∞ (MINTIMELINE+) if and only if ((V, (Eπ(i))i∈[τ]), k, 0) is a yes-instance.

Moreover, if all layers of the temporal graph are equal, then, for ℓ = 0, both problems are equivalent to an extension of k-coloring. For a graph G = (V, E) and a, b ∈ N with a ≥ b, an (a:b)-coloring of G is a function c: V → ([a] b ) such that c(u) ∩ c(v) = ∅ for all {u, v} ∈ E. Note that a (k:1)- coloring of a graph is simply a k-coloring. Given a graph G, the problem (a:b)-COLORING asks whether there is an (a:b)- coloring for G. We get the following.

Theorem 2. If E1 = E2 = · · · = Eτ , ℓ = 0, and τ ≥ k, then MINTIMELINE∞ (MINTIMELINE+) is equivalent to (τ:τ -k)-COLORING.

Proof. Suppose that T is a k-activity timeline that covers G = (V,E1, . . . ,Eτ) with E1 = · · · = Eτ =: E and ℓ = 0. We can assume that T contains exactly k intervals for each v ∈ V . Let G = (V,E). Then, c: V → ( [τ] τ-k) with c(v) := {t ∈ [τ] | (v, t, t) /∈ T } is a (τ:τ -k)-coloring of G. Conversely, if c: V → ( [τ] τ-k) is a (τ:τ - k)-coloring of G = (V,E), then T := {(v, t, t) ∈ V ×[τ]×[τ] | v ∈ V, t /∈ c(v)} is a k-activity timeline that covers G.

The NP-hardness of 3-COLORING, or (3:1)-COLORING, implies the following.

Corollary 3. MINTIMELINE∞ and MINTIMELINE+ are NP-hard, even if k = 2, ℓ = 0, τ = 3, and all layers are identical.

Bonamy et al. [2019] mention a result by Nederlof [2008] showing that (a:b)-COLORING can be solved in (b + 1)n · nO(1) time. They show that the ETH implies that there is no 2o(log b)n -time algorithm for (a:b)-COLORING [Bonamy et al., 2019, Theorem 1.1]. Thus, we have the following.

Corollary 4. MINTIMELINE∞ (MINTIMELINE+) with E1 = E2 = · · · = Eτ and ℓ = 0 cannot be solved in f(τ - k) · 2o(log(τ-k))n time for any function f unless the ETH fails.

Note that, if τ = 2 then MINTIMELINE∞ and MINTIMELINE+ are both trivial unless k = 1. Rozenshtein et al. [2021] showed that MINTIMELINE∞ is polynomial-time solvable in the case of k = 1. By contrast, we show that MINTIMELINE+ is NP-hard in the case of k = 1 and τ = 2 (strengthening the NP-hardness for k = 1 with unbounded τ by Rozenshtein et al. [2021, Proposition 3]). Moreover, MINTIMELINE∞ is FPT when parameterized by ℓ with this restriction. This gives us the following.

Theorem 5. MINTIMELINE+ with two layers is NP-hard and FPT when parameterized by ℓ.

Proof. We show NP-hardness with a reduction from ODD CYCLE TRANSVERSAL. In this problem, the input consists of a graph G = (V, E) and an integer s and the task is to decide whether there is a vertex set X ⊆ V with |X| ≤ s such that G-X is bipartite. This problem is NP-hard [Lewis and Yannakakis, 1980].

Given an instance (G = (V,E), s), the reduction outputs the instance (G := (V,E1 := E,E2 := E), k := 1, ℓ := s). If X ⊆ V with |X| ≤ s is an odd cycle transversal in G such that V1 and V2 are the two color classes in the bipartite graph G -X, then T := {(v, 1, 2) | v ∈ X} ∪ {(v, i, i) | i ∈ {1, 2}, v ∈ Vi} is a 1-activity timeline that covers G with ∑(v,a,b)∈T (b - a) ≤ s. Conversely, if T is a 1-activity timeline that covers G with ∑(v,a,b)∈T (b-a) ≤ s, then X := {v ∈ V | (v, 1, 2) ∈ T } is an odd cycle transversal of size at most s in G.

For fixed-parameter tractability, we show that MINTIMELINE+ with τ = 2 can be reduced to ALMOST 2-SAT. In this problem, the input consists of a Boolean formula ϕ in 2-CNF and an integer s and the task is to decide whether ϕ can be made satisfiable by deleting at most s clauses. The problem is known to be in FPT when parameterized by s [Razgon and O'Sullivan, 2009].

Let (G = (V,E1,E2), k, ℓ) be an instance for MINTIMELINE+. If k ̸= 1, the instance is trivial. Otherwise, we introduce two Boolean variables xv1 and xv2 for each v ∈ V . Intuitively, xvi is true if v is used to cover edges in Ei. The reduction outputs the instance (ϕ, s := ℓ), where ϕ is constructed as follows: For every edge {u, v} ∈ Ei, i ∈ {1, 2}, ϕ contains s + 1 copies of the clause (xui ∨ xvi ) expressing that the edge must be covered. For every vertex v ∈ V , the formula contains the clause (¬xv1 ∨ ¬xv2 ), stating that v can only be used once unless this clause is deleted.

Now, suppose that X is a set of at most ℓ clauses of ϕ and that α is a satisfying assignment for all other clauses. Then, T := {(v, 1, 2) | (¬xv1 ∨ ¬xv2 ) ∈ X} ∪ {(v, i, i) | α(xvi ) = true, (¬xv1 ∨¬xv2 ) /∈ X} is a 1-activity timeline that covers G with ∑(v,a,b)∈T (b-a) ≤ ℓ. Conversely, if T is a 1-activity timeline that covers G with ∑(v,a,b)∈T (b - a) ≤ ℓ, then removing the at most ℓ clauses in {(¬xv1 ∨¬xv2 ) | (v, 1, 2) ∈ T } from ϕ makes the formula satisfiable by the following assignment: α(xvi ) = true if and only if (v, i, i) ∈ T or (v, 1, 2) ∈ T .

Since MINTIMELINE∞ and MINTIMELINE+ are NP-hard, even if τ +k+ℓ is constant, the interesting parameterizations remaining involve the number n of vertices. Clearly, combining n and τ trivially yields fixed-parameter tractability for both problems, as the overall instance size is bounded in these two parameters. If we use only the number n of vertices as a parameter, then we can use dynamic programming to show that both problems are in XP.

Theorem 6 (⋆). (i) MINTIMELINE∞ is solvable in (k + 1)n (ℓ + 2)n 2n τnO(1) time and (ii) MINTIMELINE+ is solvable in (k + 1)n 2O(n) τ (ℓ + 1) time.

Note that, Theorem 6 (i) also implies that MINTIMELINE∞ parameterized by n + k + ℓ is in FPT and that Theorem 6 (ii) implies that MINTIMELINE+ parameterized by n + k is in FPT. To show that MINTIMELINE∞ is also in FPT when parameterized by n+k, we observe that it is sufficient to consider only two possibilities to cover a time-edge. This leads to a search tree algorithm similar to the one for the classical VERTEX COVER.

Theorem 7. MINTIMELINE∞ is solvable in O(2nk n2 τ) time.

Proof. Let (G = (V, (Ei)i∈[τ]), k, ℓ) be a MINTIMELINE∞ instance. We solve the instance with a search tree algorithm. To this end, we store counters kv, v ∈ V , for the number of intervals chosen for each vertex. We initially set all counters to zero and start with an empty solution T = ∅.

Let i = min{t ∈ [τ] | Et ̸= ∅} and let {u, v} ∈ Ei be an arbitrary edge (if all layers are empty, then we return "yes"). If ku = k and kv = k, then we return "no" since we cannot cover this edge. Otherwise, we simply branch into the (at most two) options of either taking (u, i, i′ ) (if ku < k) or (v, i, i′ ) (if kv < k) into T , where i′ = min(i + ℓ, τ). In each branch, we increase the corresponding counter (ku or kv) by one, delete all edges incident to the corresponding vertex (u or v) from the layers Ei, . . . ,Ei′ , and recursively proceed on the remaining instance. Clearly, the recursion terminates after at most nk calls. Thus, the running time is in O(2nk n2 τ ).

As a k-activity timeline T for a temporal graph G with n vertices is of size at most kn, Theorem 7 and Theorem 6 (ii) imply that MINTIMELINE∞ and MINTIMELINE+ are in FPT when parameterized by the solution size |T |.

We continue with disentangling the parameterized complexity of MINTIMELINE+ and MINTIMELINE∞ regarding n and ℓ in Sections 4 and 5.

4 Parameterizing MINTIMELINE+ by n+ ℓ

The main goal of this section is to show the following.

Theorem 8. MINTIMELINE+ parameterized by n + ℓ is in FPT.

The formal proof is deferred to the end of this section. The general idea behind the algorithm is to split the kactivity timeline T into two parts T0 ⊎ T>0 = T . Here, T0 contains all elements (v, a, b) ∈ T with a = b and T>0 contains all elements (v, a, b) ∈ T with a < b. Note that ∑(v,a,b)∈T0 (b-a) = 0 and that ∑(v,a,b)∈T>0 (b-a) ≤ ℓ. We observe that T>0 induces an interval graph and that the number of possible induced interval graphs is upper-bounded by a function only depending on n + ℓ. The algorithm iterates over all of these interval graphs and identifies the part of our temporal graph which can be covered by a corresponding T>0. It remains to find a T0 that covers the rest of our temporal graph. To this end, we will show that MINTIMELINE+ parameterized by n is in FPT if ℓ = 0. In fact, as both problems are equivalent if ℓ = 0, we show that MINTIMELINE∞ and MINTIMELINE+ are both in FPT when parameterized by n in this case. In the proof of Theorem 8, we will need a slightly more general version of these problems, in which there is not a single value k, but a value kv for each v ∈ V . We call this generalization NONUNIFORM MINTIMELINE∞ (MINTIMELINE+).

Lemma 9. NONUNIFORM MINTIMELINE∞ (MINTIMELINE+) parameterized by n is in FPT, if ℓ = 0.

Proof. Given I = (G = (V, (Ei)i∈[τ]), (kv)v∈V , 0), we create an integer linear program (ILP) with a number of variables bounded by some function of n. This ILP is feasible if and only if I is a yes-instance. By Lenstra's algorithm [1983], this implies that NONUNIFORM MINTIMELINE∞ (MINTIMELINE+) parameterized by n is in FPT, if ℓ = 0.

We use a variable XSE for every E ⊆ (V2 ) and S ⊆ V where S is a vertex cover for (V, E). Note that the number of these variables is at most 2(n2)+n . Intuitively, the value of the variable XSE gives us the number of times the vertex cover S is used to cover a layer with edge set E.

For E ⊆ (V2 ), let a(E) := |{t ∈ [τ] | Et = E}| denote the number of times the edge set E appears as a layer in G. Let C(E) := {S ⊆ V | S is a vertex cover of (V,E)}. Then, the ILP constraints are as follows:

As we mentioned before, we are only interested in the feasibility of this ILP, so there is no objective function to optimize.

The above ILP is feasible if and only if I is a yes-instance: Suppose that (XSE )E⊆(V2),S∈C(E) is a solution. We define a solution T of I as follows: For any E ⊆ (V2 ), let C(E) = {SE 1 , . . . , S E rE }. We use SE 1 to cover the first XS1 E appearances of (V,E) in the layers of G, that is, we add (v, t, t) to T for every v ∈ SE 1 and appearance (V,Et). Then we continue with SE 2 to cover the next XS2 E appearances, and so on. Condition (1) guarantees that T covers G and Condition (2) ensures that at most kv intervals are chosen for each vertex v ∈ V .

Conversely, suppose that I admits a solution T . For t ∈ [τ], let Xt := {v ∈ V | (v, t, t) ∈ T }. Since ℓ = 0, Xt must be a vertex cover for (V,Et). Then, set XSE := |{t ∈ [τ] | Et = E and Xt = S}|. It is easy to check that this yields a solution of the ILP.

As a side result, Theorem 2 and Lemma 9 together imply the following.

Corollary 10. (a:b)-COLORING parameterized by the number of vertices is in FPT.

We are now set to show Theorem 8: MINTIMELINE+ parameterized by n+ℓ is in FPT. The algorithm in the following proof is illustrated in Figure 2.

Proof of Theorem 8. For (G = (V, (Ei)i∈[τ]), k, ℓ), we say that an ℓ′ -pattern is a sequence (F0, . . . , Fℓ′) of edge sets where Fi ⊆ (V2 ) for all i ∈ [ℓ′ ]. A solution pattern is a pair (P, I) where P is an ℓ′ -pattern with 1 ≤ ℓ′ ≤ ℓ and I ⊆ V × {0, . . . , ℓ′ } × {0, . . . , ℓ′ } with I ̸= ∅ and a < b for all (v, a, b) ∈ I. Let P denote the set of all solution patterns. Note that there are at most 2(n2)(ℓ+1) · ℓ different ℓ′ -patterns with 1 ≤ ℓ′ ≤ ℓ. This yields |P| ≤ 2(n2)(ℓ+1)+n(ℓ+1)2 · ℓ ∈ 2O(n2 ℓ2 ) . The weight of a solution pattern (P, I) is w((P, I)) := ∑(v,a,b)∈I (b - a).

Our algorithm first checks all possibilities of how often a solution "matches" each solution pattern (P, I), that is, it uses intervals as specified by I to cover a subsequence of layers of G that is equal to P (a formal explanation follows below). Since I contains an interval with positive length, we can choose at most ℓ such solution patterns. Hence, we iterate over all functions f : P → {0, . . . , ℓ} with ∑x∈P f(x)w(x) ≤ ℓ and which have the property that ∑(P,I)∈P f((P, I))|{(v, a, b) | (v, a, b) ∈ I}| ≤ k for all v ∈ V . There are at most (ℓ+1)|P| such functions. Next, we try out every order in which the solution patterns are matched by a solution. The result is a sequence (P1, I1), . . . , (Pr, Ir) of r ≤ ℓ solution patterns. The arguments above imply that we check at most (ℓ + 1)2O(n2 ℓ2 ) · ℓ! such sequences.

Next, we check whether (P1, I1), . . . , (Pr, Ir) can be matched by a solution and, if it can, compute the temporal graph that remains to be covered once we implement the solution patterns. The above sequence can be matched by a solution if there are i1 < j1 < i2 < j2 < · · · < ir < jr ∈ [τ ] such that Ps = (Eis , . . . ,Ejs ) for all s ∈ [r]. Algorithmically, we simply determine is and js by finding the earliest occurrence of Ps in E1, . . . , Eτ with is ≥ js-1 + 1.

Next, we compute the remaining temporal graph obtained by implementing (P1, I1), . . . , (Pr, Ir) on i1, . . . , ir, j1, . . . , jr ∈ [τ]. To this end, for each s ∈ [r] and each t ∈ [is, js], let E′t := Et \ inc{v ∈ V | (v, a, b) ∈ Is, is + a ≤ t ≤ is + b}. We call G ′ := (V,E′1 , . . . ,E′τ ) the residual temporal graph. For each v ∈ V , let kv := k - ∑rs=1 |{(v, a, b) | (v, a, b) ∈ Is}|.

We now build the instance (G ′ , (kv)v∈V , 0) of NONUNIFORM MINTIMELINE+. By Lemma 9, solving this instance is FPT when parameterized by n. Our algorithm returns true if (G ′ , (kv)v∈V , 0) is a yes-instance for at least one sequence (P1, I1), . . . , (Pr, Ir).

It remains to show that the algorithm we described is correct. If the algorithm returns true, then this result is clearly correct. Assume that, for (P1, I1), . . . , (Pr, Ir), the instance (G ′ , (kv)v∈V , 0) has a solution T0. Let T>0 := ⋃rs=1 {(v, is+ a, is + b) | (v, a, b) ∈ Is}. Then, by construction, it is easy to verify that T := T0 ∪ T>0 is a solution for (G, k, ℓ).

Conversely, suppose that T is a solution for (G, k, ℓ). Let T>0 := {(v, a, b) ∈ T | a < b}. Consider the interval multiset I := {[a, b] ⊆ [τ] | ∃v ∈ V : (v, a, b) ∈ T>0} and the corresponding interval graph GI := (I,EI), where EI := {{[a, b], [a′ , b′ ]} ∈ (I2 ) | [a, b] ∩ [a′ , b′ ] ̸= ∅}. Since ∑[a,b]∈I (b - a) ≤ ℓ, it follows that GI contains at most ℓ connected components and each of these components covers at most ℓ time steps. We will describe a solution pattern corresponding to each connected component of GI. For a connected component C of GI, let i := min[a,b]∈C a and j := max[a,b]∈C b. Note that j - i + 1 ≤ ℓ. Consider the (j - i + 1)-pattern P = (Ei, . . . ,Ej). Let J := {(v, a - i, b - i) | (v, a, b) ∈ T>0, [a, b] ∈ C}. Then, the solution pattern corresponding to C is (P, J ). By listing the solution pattern for each connected component of GI in the order in which the components appear in the interval graph, we get the solution patterns (P1, I1), . . . , (Pr, Ir) where r is the number of components of GI.

We claim that our algorithm returns true for this particular sequence of solution patterns. Note that our algorithm may choose different indices i1, . . . , ir, j1, . . . , jr to implement (P1, I1), . . . , (Pr, Ir). However, the resulting residual temporal graph G ′ is the same as the residual temporal graph derived from the connected components of GI up to a permutation of the layers. Hence, by Observation 1, G ′ is also a yesinstance for NONUNIFORM MINTIMELINE+ with ℓ = 0.

5 Parameterizing MINTIMELINE∞ by n+ ℓ

In this section, we prove that fixed-parameter tractability of MINTIMELINE∞ parameterized by n + ℓ is (in contrast to MINTIMELINE+) unlikely.

Theorem 11. MINTIMELINE∞ parameterized by n is W[1]- hard for ℓ = 1.

The key difference to the case ℓ = 0 (which is in FPT (Lemma 9)) is that, for ℓ = 1, intervals can overlap and hence, the temporal ordering of the layers is relevant. We prove Theorem 11 in three steps by first showing that two generalizations of MINTIMELINE∞ with ℓ = 1 are W[1]-hard when parameterized by n. The key step is to showW[1]-hardness for the following "multicolored" version of MINTIMELINE∞.

MULTICOLORED MINTIMELINE∞

Input: A temporal graph G = (V,E1, . . . ,Eτ) where Question: Is there an activity timeline T covering G such

V = V1⊎· · ·⊎Vr, ℓ ∈ N0, and k1, . . . , kr ∈ N. that max(v,a,b)∈T (b-a) ≤ ℓ and |{(v, a, b) ∈ T | v ∈ Vi}| ≤ ki for all i ∈ [r]?

The proof is by reduction from UNARY BIN PACKING, where we are given m items with sizes s1, . . . , sm ∈ N, a number β ∈ N of bins, and a bin size B ∈ N with all integers encoded in unary. We are asked to decide if there is an assignment f : [m] → [β] of items to bins such that ∑i∈f -1 (b) si ≤ B for all b ∈ [β]. This problem is W[1]-hard when parameterized by β [Jansen et al., 2013]. The general idea behind the reduction is that bins can be represented by vertices and the bin size by the color budgets ki. The complete proof is deferred to the full version.

Lemma 12 (⋆). MULTICOLORED MINTIMELINE∞ parameterized by n is W[1]-hard for ℓ = 1.

Recall the definition of NONUNIFORM MINTIMELINE∞ given in Section 4. Using Lemma 12, we can now show that it is W[1]-hard when parameterized by n for ℓ = 1. The proof is deferred to the full version.

Lemma 13 (⋆). NONUNIFORM MINTIMELINE∞ parameterized by n is W[1]-hard for ℓ = 1.

To prove Theorem 11, we now show how to reduce NONUNIFORM MINTIMELINE∞ to MINTIMELINE∞.

Proof of Theorem 11. We reduce from NONUNIFORM MINTIMELINE∞. Given an instance (G = (V = {v1, . . . , vn}, (Et)t∈[τ]), ℓ = 1, (kv)v∈V ), we construct an instance (G ′ = (V ′ , (E′t )t∈[τ ′ ]), ℓ = 1, k) of MINTIMELINE∞. We let V ′ := V ∪ {u1, u2}, τ ′ := τ + 2k(|V | + 2), and k := maxv∈V kv. The layers of G ′ are as follows: For t ∈ [τ], we let E′t := Et. The layers E′τ+1 , . . . ,E′τ+4k only contain the edge {u1, u2}. Then, for i ∈ [n], the layers E′τ+2k(i+1)+1 , . . . ,E′τ+2k(i+1)+2(k-kvi ) contain only the edge {vi, u1}, while the layers E′τ+2k(i+1)+2(k-kvi )+1 , . . . , E′τ+2k(i+2) are empty.

Suppose that T is an activity timeline that covers G and contains only kv intervals that use v for each v ∈ V . Then, we construct a k-activity timeline T ′ that covers G ′ as follows. We include all intervals in T . We add (u1, τ +2a-1, τ +2a) and (u2, τ + 2k + 2a - 1, τ + 2k + 2a) for all a ∈ [k] and (vi, τ+2k(i+1)+a-1, τ+2k(i+1)+a) for all a ∈ [k-kv]. Now suppose that T ′ is a k-activity timeline that covers G ′ . First, T ′ must contain k intervals that use u1 and k intervals that use u2 in order to cover the appearances of the edge {u1, u2} in E′τ+1 , . . . , E′τ+4k . Hence, the edges {u1, vi} can only be covered by intervals that use vi. This requires k-kvi intervals that use vi. Hence, T := {(v, a, b) ∈ T ′ | a ∈ [τ], v ∈ V } is an activity timeline that covers G and only contains kv vertices that use each v ∈ V .

Unless the ETH fails, UNARY BIN PACKING cannot be solved in time f(β)|I|o(β/ log β) for any function f, where |I| is the input size [Jansen et al., 2013, Theorem 3]. That our reduction yields a temporal graph with O(β) vertices implies: Corollary 14. Unless the ETH fails, MINTIMELINE∞ cannot be solved in time f(n)|G|o(n/ logn) , for any function f, even if ℓ = 1.

6 Conclusion

We completely settled the computational complexity of MINTIMELINE∞ regarding the considered parameters. For MINTIMELINE+, the open question remaining is whether it is in FPT when parameterized by the number of vertices. Besides this question, there are many others which could be studied in future work:

• Are there (polynomial) kernelizations for the FPT cases? Developing data reduction rules might be especially interesting from a practical perspective.
• Which other parameters yield tractable special cases? For example, can the number of vertices be replaced by a smaller parameter (e.g. the vertex cover number or the treewidth of the underlying graph)?
• What changes if one only bounds the overall number of activity intervals instead of bounding for each vertex? It should be possible to modify all our algorithms to solve this problem. Maybe some of our hard cases become tractable?
• What about "temporalizing" other vertex selection problems (like DOMINATING SET) in an analogous way (that is, at each time step the set of active vertices must be a valid selection for the current graph)? In fact, our dynamic programs and the ILP should easily work here as well, since they do not specifically depend on vertex covers.

Acknowledgments

This work was initiated at the research retreat of the Algorithmics and Computational Complexity group, TU Berlin, held at Zinnowitz, September 2021. The second author is supported by the DFG Research Training Group 2434 "Facets of Complexity".