key: cord-0044031-bgstpile
authors: Campos, Victor; Lopes, Raul; Marino, Andrea; Silva, Ana
title: Edge-Disjoint Branchings in Temporal Graphs
date: 2020-04-30
journal: Combinatorial Algorithms
DOI: 10.1007/978-3-030-48966-3_9
sha: 3e81ce1b1849aabd77c3611c5e7225a2aa39254d
doc_id: 44031
cord_uid: bgstpile

A temporal digraph [Formula: see text] is a triple [Formula: see text] where G is a digraph, [Formula: see text] is a function on V(G) that tells us the time stamps when a vertex is active, and [Formula: see text] is a function on E(G) that tells for each [Formula: see text] when u and v are linked. Given a static digraph G, and a subset [Formula: see text], a spanning branching with root R is a subdigraph of G that has exactly one path from R to each [Formula: see text]. In this paper, we consider the temporal version of Edmonds’ classical result about the problem of finding k edge-disjoint spanning branchings respectively rooted at given [Formula: see text]. We introduce and investigate different definitions of spanning branchings, and of edge-disjointness in the context of temporal graphs. A branching [Formula: see text] is vertex-spanning if the root is able to reach each vertex v of G at some time where v is active, while it is temporal-spanning if v can be reached from the root at every time where v is active. On the other hand, two branchings [Formula: see text] and [Formula: see text] are edge-disjoint if they do not use the same edge of G, and are temporal-edge-disjoint if they can use the same edge of G but at different times. This lead us to four definitions of disjoint spanning branchings and we prove that, unlike the static case, only one of these can be computed in polynomial time, namely the temporal-edge-disjoint temporal-spanning branchings problem, while the other versions are [Formula: see text]-complete, even under very strict assumptions.

In this paper, we refer to digraphs in the classical sense as static digraphs. A temporal digraph is a digraph that exists and changes in a time interval T . That is, given a static digraph G, a temporal digraph G with base static digraph G and lifetime T changes as follows: at each time stamp t ∈ T , only a subdigraph of G is active, and edges might have a delay, leaving a vertex at some time stamp but arriving only later. If a vertex v ∈ V (G) is active at every t ∈ T , we say that v is permanent.

In this paper we deal with disjoint spanning branchings in temporal digraphs, which are well-understood structures in digraphs. Given a digraph G, and a subset R ⊆ V (G), we say that H ⊆ G is a spanning branching of G with root R if V (H) = V (G), and H contains exactly one path between some r ∈ R and u, for each u ∈ V (G). Given subsets R 1 , · · · , R k , a classical result by Edmonds [9] gives a necessary and sufficient condition for the existence of k edge-disjoint branchings with roots R 1 , · · · , R k , respectively. His result also gives a polynomial algorithm that constructs these branchings.

When translating concepts to temporal graphs, it is often the case that theorems coming from graph theory, in the classical sense, can hold or not depending on the adopted definition. Indeed, in [14] the authors give an example where Edmonds' result on branchings does not hold on the temporal context. However, as we will see later, their concept is just one of many possible definitions, and in fact there is even one case where polynomiality holds.

Another example of such behavior is the validity of Menger's Theorem. It has been shown that the edge version of Menger's Theorem holds [3] , even if one considers weights on the edges [2] . However, the vertex version of Menger's Theorem holds or not, depending on how one interprets what a cut should be. If a cut is understood as a subset of V (G), then Menger's Theorem does not hold [3, 14] ; and if it is understood as a subset of the appearances of vertices in time (alternatively, a cut can be seen as deactivating vertices at some time stamps), then Menger's Theorem holds [18] .

Our Contribution. Given a temporal digraph G with base digraph G, and subsets of vertices in time R 1 , · · · , R k , i.e. sets of pairs (u, t) where u is a vertex of G and t a time stamp, here we investigate the many variations of finding (pairwise) disjoint spanning branchings with roots R 1 , · · · , R k . Spanning can mean that one wants to pass by at least one appearance of each u ∈ V (G) (called vertex spanning), or by all appearances of each u ∈ V (G) (called temporal spanning). Similarly, edge-disjoint can have different interpretations, as it can refer to edges of G or to the appearances of these edges in G. We say that two branchings are edge-disjoint if they do not share any edge of G, and that they are temporaledge-disjoint (or t-edge-disjoint for short) if they do not share any appearance of an edge of G in G. We found that the only case in which this problem is polynomial (as its static counterpart) is when we want t-edge-disjoint temporalspanning branchings. We also found that if vertices are permanent (this is the more popular case where vertices are always active), the problem is polynomial for temporal-spanning branchings and NP-complete otherwise. Our results are summarized in Table 1 and detailed in the following main theorem. A digraph G is a in-star if there exists u ∈ V (G) such that all the edges in G are incoming edges to u. As said before, Edmonds' condition is the characterization behind the polynomial algorithm for finding k edge disjoint spanning branchings in digraphs. Because of our NP-completeness results, it is worth remarking that, unless P=NP, any such characterization for the NP-complete cases in temporal digraphs should be checkable in superpolynomial time, unlike the one provided by Edmonds.

Finally, our reductions further imply that, in the case of edge-disjoint temporal-spanning, even if the base digraph G is a in-star, the problem cannot be solved by an algorithm running in time O * (2 o(T ) ) unless ETH fails, where T is the lifetime of G. Moreover, in the vertex-spanning variations, the problem also cannot be solved in O * (2 o(n+m) ) under the same assumption, where n and m are respectively the number of nodes and edges of the base digraph of G.

Related Work: While it is easy to imagine a variety of graph problems that can profit from considering changes in time, it is hard to pin-point when the study of temporal graphs and similar structures began. Nevertheless, in the last decade or so, it has attracted a lot of attention from the community, with a considerable number of papers being published in the field (we refer the reader to the surveys [15, 19] ). We mention that temporal graphs (or other very similar structures) appear in the literature under a number of names, such as dynamic networks [4] , time-varying graphs [8] , evolving networks [5] , and link streams [15] . Also, many works consider a temporal graph G as having vertices that are always active, and edges have the same starting and ending time [2, 6, 14, 18, 20] . While models where edges that have a delay are more common [8, 25] , models where nodes can be inactive have already been considered in [8, 15] .

A path in temporal graphs is generally understood as a sequence of edges respecting time, i.e. the arrival time in each vertex of the path must be lower than the departing time of the next edge taken. In this context, a number of metrics can be related to a path, such as earliest arrival time, latest departure time, minimum number of temporal edges, and minimum traveling time [25] . When vertices can be inactive, we have to further ensure that, when waiting for the next edge on a certain vertex, it must remain active in the waiting period [8] . In this scenario, the definitions of reachability and connectivity change accordingly, and it is natural to ask how well-known structures and results from graph theory in the classical sense change taking into account the temporal constraint.

Temporal definitions of trees [6, 15] and (minimum) spanning trees [13] , which are related to our definition of branching, have been proposed and investigated, and usually consist of ensuring that the root-to-node path in the tree is a valid temporal path. Analogously, temporal cuts from a vertex s to t aim to break any temporal path from s to t and can be related to extending the max-flow min-cut Theorem to temporal graphs [2] . And as we have already mentioned, different conclusions have been made about a temporal version of Menger's Theorem depending on the adopted translation in terms of temporal graphs [3, 14, 18] .

Edmonds' Theorem on disjoint branchings is a classical theorem in graph theory, with many distinct existing proofs (e.g. Lovász [16] , Tarjan [24] , and Fulkerson and Harding [12] ), and has many interesting consequences on digraph theory (e.g., one can derive Menger's Theorem from it, characterize arcconnectivity [22] , characterize branching cover [11] , ensure integer decomposition of the polytope of branchings of size k [17] , etc). As far as we know, the only other time that Edmonds' Theorem has been investigated on the temporal context has been in [14] , where the authors give an example where the theorem does not hold. The definition used by them falls into our category of edge-disjoint vertex-spanning branchings, which we prove to be NP-complete even under very strict constraints.

Structure of the Paper. The paper is organized as follows. In Sect. 2, we formalize the definitions of spanning branchings and disjointness, also showing that having multiple roots in each of the k branchings is computationally equivalent to having a single root for all of the k branchings. In Sect. 3, we present the results about temporal-spanning branchings. In Sect. 4 we present our results concerning vertex-spanning branchings. Finally, in Sect. 5, we draw our conclusions and make some final remarks. The proofs of the results marked with '( )' can be found online in [7] .

This section is devoted to formally define the several concepts of temporal graphs and disjoint branchings we introduce in this paper. A temporal digraph G is a triple (G, γ, λ) where G is a digraph and γ and λ are functions on V (G) and E(G), respectively, that tell us when the vertices and the edges appear. More

Here, we consider only finite temporal digraphs, i.e., T = max v∈V (G) γ(v) is defined and is called the lifetime of G. We call G the base digraph of G. In what follows, unless said otherwise, we work on general digraphs, i.e., directions, loops and multiple edges are allowed.

In

, and t = t for every (t, t ) ∈ λ(E(G)), then the above definition corresponds to the definition of temporal graph given in [14] and many other works. The above definition also generalizes the definition of stream graph given in [15] , and of time-varying graphs given in [1] .

The vertices and edges of G are the vertices and edges of G. We say that a vertex v is active

. This is similar to what has been proposed in [1] and [2] . We call the digraph G T the (γ, λ)-digraph of G.

Since in our more general case, also vertices appear and disappear, the definition of walk must take into account that it is possible to wait only on vertices which are active, as formally defined next. Given temporal vertices s 1 , s k ∈ V T , an s 1 , s k -temporal walk in (G, G T ) is a sequence of temporal vertices and temporal edges, (s 1 , . . . , s k ), that either goes through a temporal edge, or stays on different copies of the same vertex of G. More formally: if s i is a temporal edge, then s i−1 and s i+1 are temporal vertices and s i goes from s i−1 to s i+1 ; and if s i and s i+1 are temporal vertices, then s i = (v, t) and s i+1 = (v, t + 1) for some vertex v and some time t. If such a walk exists, we say that s 1 reaches s k .

Given two branchings B 1 = (G 1 , γ 1 , λ 1 ) and B 2 = (G 2 , γ 2 , λ 2 ) rooted at R 1 , R 2 , respectively, either both temporal-spanning or both vertex-spanning, we say that B 1 and B 2 are temporal-edge-disjoint (or t-edge-disjoint for short) if they have no common temporal edges; more formally, if λ 1 (e) ∩ λ 2 (e) = ∅ for every e ∈ E(G). And we say that B 1 and B 2 are edge-disjoint if there is no edge uv ∈ E(G) that has copies in both B 1 and B 2 ; more formally, E(G 1 )∩E(G 2 ) = ∅.

{temporal, vertex}, and k be a fixed positive integer. Given a temporal digraph G, and subsets of temporal vertices

We introduce the following restriction of Problem 1, which corresponds to finding branchings that have a single root (also called out-arborescence).

vertex}, and k be a fixed positive integer. Given a temporal digraph G, and a temporal vertex r ∈ V T , find k X-disjoint Y -spanning branchings B 1 , . . . , B k each one with root r.

Proof. Problem 2 is clearly a restriction of Problem 1. In the following we provide the reduction in the opposite direction, from the problem where each branching has a subset of V T as roots to the problem where each branching has a single same root. For this, for each i ∈ [k] add a new vertex r i to G adjacent to every u ∈ V (G) such that (u, t) ∈ R i , for some t ∈ [T ]. Then, make γ(r i ) = {0}, and for each (u, t) ∈ R i , add (0, t) to λ(r i u) (which is the same as adding the temporal edge (r i , 0)(u, t) to G). Moreover, add a vertex r and make it adjacent to {r 1 , · · · , r k }; also make γ(r) = {0} and λ(rr i ) = {(0, 0)} (which is the same as adding temporal edges (r, 0)(r i , 0) for every i ∈ [k]).

One can see that k vertex-spanning (resp. temporal-spanning) branchings rooted at r give k vertex-spanning (resp. temporal-spanning) branchings rooted at R 1 , · · · , R k , and vice-versa. The edge-disjointness, both for t-edge or edgedisjoint versions, clearly are not altered by adding the new temporal edges.

The next easy proposition tells us that if finding k disjoint spanning branchings is hard, for some fixed k, then so is finding k + 1 of them. Proof. To reduce from k to k + 1, it suffices to add R k+1 = V T as entry. Surely the (k +1)-th branching has no temporal edges, which means that the other ones form a solution to the initial problem.

This section is devoted to study Problem 1 in the case where Y is temporal, i.e. we aim to find k X-disjoint temporal-spanning branchings, with X ∈ {edge, t-edge}. We will hence prove Item 1 and Item 2 of Theorem 1 respectively in Sect. 3.1 and in Sect. 3.2.

Let G = (G, γ, λ), and let V T , E T be its set of temporal vertices and edges, respectively. Also, let R 1 , · · · , R k ⊆ V T , and H = (V T , E T ∪ E ), where E contains k copies of the edge (u, t)(u, t + 1) whenever {(u, t), (u, t +1)} ⊆ V T . We prove that G has the desired branchings iff H has k edge-disjoint spanning branchings with roots R 1 , · · · , R k . Then, Item 1 of Theorem 1 follows by Edmonds' result [9] . G = (G, γ, λ) be a temporal digraph, R 1 , · · · , R k ⊆ V T , and H be constructed as above. Then, G has k t-edge-disjoint temporal-spanning branchings rooted at R 1 , · · · , R k iff H has k edge-disjoint spanning branchings rooted at R 1 , · · · , R k .

Proof. Let B 1 , · · · , B k be t-edge-disjoint temporal-spanning branchings rooted at R 1 , · · · , R k , respectively. For each B i , let B i be a spanning subgraph of H initially containing the temporal edges of B i ; then for each (u, t) ∈ V (B i ), if the only walk in B i from R i to (u, t) contains (u, t)(u, t + 1) as a subsequence, then add an unused copy of (u, t)(u, t + 1) ∈ to B i . Because this walk is unique and cannot pass twice from time stamp t to time stamp t + 1, we get that at most k copies are needed, and, hence, the produced branchings are edge-disjoint. The converse can be easily proved by deleting the edges in E from the solution to obtain the temporal subgraphs.

In this section, we prove Item 2 of Theorem 1. For this, we first prove that the problem is NP-complete, and then that it is polynomial when each vertex is active for a consecutive set of time stamps. This includes the popular case where vertices are assumed to be permanent, as well as the case where T = 2.

Theorem 2 and Theorem 3 below detail our NP-completeness results. In the next proof, we make a reduction from the k-Weak Disjoint Paths problem (k-WDP), where we are given a digraph G and a set I of k pairs of vertices {(s 1 , t 1 ), . . . , (s k , t k )} (called the requests) of V (G) and the goal is to find a collection of pairwise edge-disjoint paths {P 1 , . . . , P k } such that P i is a path from s i to t i in G, for i ∈ {1, . . . , k}. The k-WDP problem is NP-complete for k = 2 [10] and W[1]-hard with parameter k in DAGs [23] . ≥ 2 be a fixed integer, G = (G, γ, λ) be a temporal digraph, and R 1 , . . . , R k ⊆ V T . Deciding whether G has k edge-disjoint temporal-spanning branchings rooted at R 1 , · · · , R k is NP-complete even if G has lifetime 3.

Proof. Let (G, I) be an instance of 2-WDP with I = {(s 1 , t 1 ), (s 2 , t 2 )}, and define W = {s 1 , t 1 , s 2 , t 2 }. Assume that s 1 , s 2 are sources, t 1 , t 2 are sinks, and all vertices in W are distinct. We construct the temporal graph G = (G, γ, λ) with subsets R 1 , R 2 such that G has 2 edge-disjoint temporal-spanning branchings rooted at R 1 , R 2 if and only if (G, I) is a "yes" instance of 2-WDP. The NPcompleteness for higher values of k follows from Proposition 1.

In the constructed temporal graph, there are no temporal edges of the type (u, t)(v, t ) with t = t . For this reason, it is easier to describe our temporal graph by describing, for each timestamp, what are the vertices and edges that are active. These are called snapshots and consist of subgraphs of G formed at each timestamp.

We let the first snapshot of G initially consist of G − {s 2 , t 2 }, and the third snapshot initially consist of G − {s 1 , t 1 }. Then, we add a new vertex x to snapshot 1, and add the edges:

Similarly, we add a new vertex y to snapshot 3, and add the edges: Fig. 1 . Define R 1 = {(s 1 , 1), (y, 3)} and R 2 = {(s 2 , 3), (x, 1)}. Now, we prove that (G, I) is a "yes" instance of 2-WDP if and only if G contains two edge-disjoint temporal-spanning branchings rooted at R 1 and R 2 , respectively. Notice that snapshot 2 of G is empty, thus each path in G can be represented by either a temporal path on snapshot 1 or a temporal path on snapshot 2.

First, let P 1 and P 2 be two edge-disjoint paths from s 1 to t 1 and from s 2 to t 2 in G, respectively. Let T 1 be initially the copy of P 1 in snapshot 1, and T 2 be initially the copy of P 2 in snapshot 3. Note that the vertices not spanned by T 1 are all the copies of v / ∈ V (P 1 ) in snapshot 1, together with all the vertices in snapshot 3, and vertices {(x, 1), (y, 3)}. To span snapshot 3, add to T 1 all edges between (y, 3) and (v, 3), for every v ∈ V (G) \ {s 1 , t 1 }. To span the remainder of snapshot 1, add all edges between (t 1 , 1) and (v, 1), for every v ∈ V (G) \ (V (P 1 ) ∪ {s 2 , t 2 }), and the edge from (t 1 , 1) to (x, 1). A similar argument can be applied to span every temporal vertex also with T 2 . Because P 1 and P 2 are edge-disjoint, we get that T 1 and T 2 could only intersect in the added edges, which does not occur because all edges added to T 1 are incident to t 1 and y, all edges added to T 2 are incident to t 2 and x, and there is no intersection between these. Now, let T 1 and T 2 be edge-disjoint temporal-spanning branchings in G with roots R 1 , R 2 . Denote snapshot 1 by G 1 . Since t 1 appears only in G 1 , and the only root of R 1 in G 1 is (s 1 , 1), we get that in T 1 there exists a path of G 1 going from (s 1 , 1) to (t 1 , 1). Because the only incoming edge to (x, 1) is (t 1 , 1)(x, 1), we get that (x, 1) cannot be an internal vertex in this path, and hence it corresponds to a path in G, P 1 . Applying a similar argument, we get a path P 2 from s 2 to t 2 in G taken from T 2 , and since T 1 and T 2 are edge-disjoint, so are P 1 and P 2 .

The next result concludes the proof of Item 2 of Theorem 1. Let k ≥ 2 be a fixed integer, G = (G, γ, λ) be a temporal digraph, and R 1 , . . . , R k ⊆ V T . Deciding whether G has k edge-disjoint temporalspanning branchings rooted at R 1 , · · · , R k is NP-complete, even if G is a instar, and each snapshot has constant size. Furthermore, in this case, there is no algorithm running in time O * (2 o(T ) ) to solve the problem, unless ETH fails.

The following theorem gives us a situation where the problem becomes easy. Note that this case includes the temporal graphs used in [2, 6, 14, 18, 20] , where vertices are assumed to be permanent. It also implies that the problem is polynomial when the lifetime of G is 2, which together with Theorem 2, gives a complete dichotomy in terms of the lifetime of G. G = (G, γ, λ) be a temporal digraph with temporal vertices V T , and let R 1 , · · · , R k ⊆ V T . If for every v ∈ V (G), γ(v) is exactly one interval of consecutive integers, then finding k edge-disjoint temporal-spanning branchings rooted at R 1 , · · · , R k can be done in polynomial time.

Proof. Let T be the lifetime of G. We first construct digraphs G 0 , · · · , G T and subsets R j 1 , · · · , R j k for each j ∈ {0, · · · , T }, then we prove that G has the desired branchings if and only if G j has k edge-disjoint branchings rooted at R j 1 , . . . , R j k for each j ∈ {0, · · · , T }, which can be checked in polynomial time, applying Edmonds' result [9] .

Also, for every i ∈ [k], let R 0 i be the roots at time stamp 0, i.e., the set {u ∈ V (G) | (u, 0) ∈ R i }. Now, for each j ∈ [T ], let G j = (V j , E j ) be the digraph containing the edges arriving at time stamp j together with their endpoints; more formally, E j = {e ∈ E(G) | (t, j) ∈ λ(e), for some t} and V j = {u ∈ V (G) | (u, j) ∈ V T or uv ∈ E j , for some v}. Also, for each i ∈ [k], let R j i be the set of roots at time stamp j together with vertices still active from the previous time stamp, i.e.,

Now, let B 1 , · · · , B k be edge-disjoint temporal-spanning branchings rooted at R 1 , · · · , R k ; denote by E T (B i ) the set of temporal edges of B i . Consider j ∈ {0, · · · , T }, and for each i ∈ [k], let B j i be the set of edges of B i that have a copy ending at time stamp j, i.e.,

Because B 1 , · · · , B k are edge-disjoint, we get that B j 1 , · · · , B j k are also disjoint. It remains to prove that each B j i is the edge set of a spanning branching of G j rooted at R j i . So, consider any i ∈ [k]. Because B i is a temporal-spanning branching of G, we know that each u ∈ V (G) is either the head of some edge in B j i , in which case u is spanned by B j i , or u is a root in B j i . We prove that in the latter case we get that u ∈ R j i . Because u is not the head of any edge in B j i , this means that either (u, j) ∈ R i or (u, j) is spanned by B i just by waiting, i.e., {j − 1, j} ⊆ γ(u). In both cases, we get that u ∈ R j i , as we wanted to prove. Now, for each j ∈ {0, · · · , T }, let B j 1 , . . . , B j k be the edge sets of k edgedisjoint spanning branchings of G j . First, we prove that if uv ∈ B j i , then v ∈ R j i for every i ∈ [k] and every j ∈ {j + 1, · · · , T } ∩ γ(v); hence if B i = T j=0 B j i , then we get that B 1 , · · · , B k are disjoint (these will be used later to construct the desired temporal branchings). So let j ∈ {j + 1, · · · , k} ∩ γ(v) and observe that if uv ∈ E(G j ) then j ∈ γ(v). Because γ(v) is an interval of consecutive integers and j < j ∈ γ(v), we get that j − 1 ∈ γ(v), which implies that v ∈ R j i for every i ∈ [k], as we wanted to show. Now, for each i ∈ [k], let B i = (G, γ, λ i ) be a spanning temporal subdigraph of G having as temporal edges the temporal copies of each e ∈ B i , i.e, λ i (e) = λ(e) if e ∈ B i , and λ i (e) = ∅ otherwise. Because B 1 , · · · , B k are disjoint, it follows that B 1 , · · · , B k are edge-disjoint, so it remains to prove that each B i is a temporal-spanning branching rooted at R i . Let u ∈ V (G), and recall that γ(u) is an interval of consecutive integers; denote by s u the minimum value in γ(u). Note that we just need to prove that if (u, s u ) / ∈ R i , then there exists a temporal edge in B i arriving in (u, s u ); this is because the other copies can be spanned simply by waiting in the interval γ(u). Since (u, s u ) / ∈ R i and s u − 1 / ∈ γ(u), we get that u / ∈ R su i . So, let vu ∈ B su i (it exists since B su i is the edge set of a spanning branching of G su ), and recall that λ i (vu) = λ(vu). We know that vu ∈ E(G su ) only if (v, j)(u, s u ) is a temporal edge of G for some j ≤ s u (i.e. (j, s u ) ∈ λ(vu)). This means that there is a temporal edge arriving in (u, s u ) in B i , completing the proof.

In this section, we provide an NP-completeness proof to prove both Item 3 and Item 4 of Theorem 1. We make a reduction from NAE-SAT, which consists of, given a CNF formula φ such that each clause contains exactly 3 literals, deciding whether there is a truth assignment to φ such that each clause has at least one true and one false literal. This is problem is NP-complete [21] , and in fact it is a well known standard procedure to make a reduction from 3-SAT to it that produces a formula of size linear on the size of the original 3-SAT formula. Therefore, applying ETH we get that NAE-SATalso cannot be solved in time O (2 o(n+m) ) where n, m are the number of variables and clauses of an input, respectively.

Let φ be a CNF formula on variables {x 1 , . . . , x n } and clauses {c 1 , . . . , c m }. A variable gadget related to x i is formed by the set of vertices

Now, consider a clause c i = { i1 , i2 , i3 }, and for each i ∈ [3] let x ij be the variable related to literal ij . For each i ∈ [3] , if x ij appears positively in c i , then add edge T ij c i to the clause gadget related to c i ; otherwise, add edge F ij c i . See Fig. 2 for the digraph related to φ = (

Denote by C i the set of vertices in the clause gadget of c i , and by E i , the set of edges. Now, let G φ be the digraph formed by the union of all variable and clause gadgets, i.e., 

Theorem 5. For each k ≥ 2, given a temporal digraph G = (G, γ, λ) with lifetime T , and set of temporal vertices V T , and subsets R 1 , · · · , R k ⊆ V T , it is NP-complete to decide whether G has k (t-edge-disjoint or edge-disjoint) vertexspanning branchings rooted at R 1 , · · · , R k , even if T = 2 and G is a DAG. Furthermore, letting n = |V (G)| and m = |E(G)|, no algorithm running in time O * (2 o(n+m) ) can exist for the problem, unless ETH fails.

Proof. The second part follows easily since the reduction is linear. We prove the theorem for k = 2, and NP-completeness for bigger values of k follows by Lemma 1. Let φ be an instance of NAE-SAT, and let G be the temporal digraph constructed as before; denote by G the base digraph. We prove that φ is a "yes" instance if and only if G has k edge-disjoint vertex-spanning branchings rooted at {(g, 1), (r, 1)} (we will see that the branchings are also t-edge disjoint).

First, suppose that φ is a "yes" instance of NAE-SAT. We construct a solid and a dotted branching that satisfy our conditions. For each true variable x i , add to the solid branching the following edges of snapshot 1: {gx i , x i T i , T i a i }, together with edge T i c j for each clause c j containing x i that is not reached by the solid branching yet; also add to the dotted branching edges {rx i , x i F i , F i a i }, , together with edge F i c j for each clause c j containing x i that is not reached by the dotted branching yet. Do something similar to the false variables, but switching the branchings. Figure 2 gives the branchings related to the assignment (T, T, F, F ) to (x 1 , x 2 , x 3 , x 4 ), respectively.

Observe that every u ∈ V (G) is spanned by both branchings, with the exception of vertices in B = {(T i , 2), (F i , 2) | i ∈ [n]}. However, these can easily be spanned in the second snapshot since {(g, 2), (r, 2)} is complete to B. Now, let B 1 , B 2 be two edge-disjoint vertex-spanning branchings. Because each a i can only be reached at the first snapshot, it is reached by exactly two paths from {(g, 1), (r, 1)}, one of them going through (x i , 1)(T i , 1) and the other through (x i , 1)(F i , 1). We then put x i as true if and only if (x i , 1)(T i , 1) is in branching B 1 . Now, consider clause c i = ( i1 ∨ i2 ∨ i3 ). One can verify that, because c i is spanned by B 1 and B 2 , we get that at least one of the edges in E i is in B 1 , and at least one in B 2 , which implies that at least one of i1 , i2 , i3 is true, and at least one is false, as desired.

In this paper we have investigated the temporal version of Edmonds' classical result about the problem of finding k edge-disjoint spanning branchings rooted at given R 1 , · · · , R k . We have introduced different definitions of spanning branchings, and of edge-disjointness in temporal digraphs. We have proved that, unlike the static case, only one of the these can be computed in polynomial time, namely the temporal-edge-disjoint temporal-spanning branchings problem, while the other versions are NP-complete under very strict constraints. Given a temporal digraph G = (G, γ, λ), in the particular case of edge-disjoint temporal-spanning, we give separate NP-complete results for fixed lifetime, and for when G is a in-star. A good question then might be whether there exists a polynomial algorithm for fixed lifetime and treewidth (a in-star has treewidth 1).

Another interesting question is whether the problem remains hard for fixed lifetime when the base digraph is a DAG. Also, as we have provided computational lower bounds under ETH in Theorem 3 and in Theorem 5, we wonder whether there exist algorithms matching these lower bounds.

Time-varying graphs and dynamic networks

Temporal flows in temporal networks

Vulnerability of scheduled networks and a generalization of Menger's theorem

Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks

Evolving networks

Computing shortest, fastest, and foremost journeys in dynamic networks

Edge-disjoint branchings in temporal graphs. arXiv e-prints

Time-varying graphs and dynamic networks

Edge-disjoint branchings

The directed subgraph homeomorphism problem

Covering branchings

On edge-disjoint branchings

Minimum spanning trees in temporal graphs

Connectivity and inference problems for temporal networks

Stream graphs and link streams for the modeling of interactions over time

On two minimax theorems in graph

Integral decomposition in polyhedra

Temporal network optimization subject to connectivity constraints

An introduction to temporal graphs: an algorithmic perspective

Timevarying graphs and social network analysis: temporal indicators and metrics

The complexity of satisfiability problems

Edge-disjoint branching in directed multigraphs

Parameterized tractability of edge-disjoint paths on directed acyclic graphs

A good algorithm for edge-disjoint branching

Path problems in temporal graphs