key: cord-0609441-jdvwx8vj
authors: Thejaswi, Suhas; Lauri, Juho; Gionis, Aristides
title: Restless reachability problems in temporal graphs
date: 2020-10-16
journal: nan
DOI: nan
sha: d7c560dc8f94ddbf937e012d1ea2da0f844d89cf
doc_id: 609441
cord_uid: jdvwx8vj

We study a family of reachability problems under waiting-time restrictions in temporal and vertex-colored temporal graphs. Given a temporal graph and a set of source vertices, we find the set of vertices that are reachable from a source via a time-respecting path, where the difference in timestamps between consecutive edges is at most a resting time. Given a vertex-colored temporal graph and a multiset query of colors, we find the set of vertices reachable from a source via a time-respecting path such that the vertex colors of the path agree with the multiset query and the difference in timestamps between consecutive edges is at most a resting time. These kind of problems have several applications in understanding the spread of a disease in a network, tracing contacts in epidemic outbreaks, finding signaling pathways in the brain network, and recommending tours for tourists. We present an algebraic algorithmic framework based on constrained multilinear sieving for solving the restless reachability problems we propose. In particular, parameterized by the length of a path $k$ sought, we show the problems can be solved in $O(2^k k m Delta)$ time and $O(n tau)$ space, where $n$ is the number of vertices, $m$ the number of edges, $Delta$ the maximum resting time and $tau$ the maximum timestamp of an input temporal graph. In addition, we prove that the algorithms presented for the restless reachability problems in vertex-colored temporal graphs are optimal under plausible complexity-theoretic assumptions. Finally, with an open-source implementation, we demonstrate that our algorithm scales to large graphs with up to one billion temporal edges, despite the problems being NP-hard. Specifically, we present extensive experiments to evaluate our scalability claims both on synthetic and real-world graphs.

Graphs are used to model many real-world problems such as information propagation in social networks [5, 41] , spreading of epidemics [3, 58, 64] , protein interactions [2, 67] , activity in brain networks [15, 25, 33] , and design of nano-structures using DNA [6] . However, real-world problems often entail complex interactions whose semantics are not captured by usual simple graph models. As such, over the years, researchers have enriched graph models by introducing (i) node and edge attributes giving rise to attributed graphs [61, 75] or (ii) edge timestamps giving rise to temporal graphs [37, 56] . In particular, temporal graphs are used to model complex phenomena and network dynamics in a wide range of applications related to social networks, genealogical trees, transportation and telecommunication networks.

As with any graph model, connectivity is a fundamental problem in temporal graphs. That is, the basic question when analyzing the structure of a given temporal graph is the question of whether two vertices are connected by a temporal path [37, 56] . A temporal path, or time-respecting path, is a path in which consecutive edges have nondecreasing timestamps. An extension to connectivity is reachability, where the goal is to find the connectivity between all pairs of vertices [36] . Some variants of connectivity and reachability problems such as finding the path that minimizes the length or arrival time can be solved in polynomial time [21, 36, 81] . However, recently Casteigts et al. [17] showed that a variant of the connectivity problem with waiting/resting time restrictions, known as restless temporal path (or more simply restless path if the context is clear) is NP-hard. A restless path is a temporal path such that the time difference of consecutive edges is at most a resting time.

In this paper we study a family of reachability problems in temporal graphs with waiting/resting time restrictions. In more detail, we study the following problems:

• Restless path (RestlessPath): Given a temporal graph, a source, and a destination, decide if there exists a restless path connecting the source and the destination. • Short restless path ( -RestlessPath): Given a temporal graph, a source, a destination, and an integer , decide if there exists a restless path of length − 1 connecting the source and the destination. • Short restless motif ( -RestlessMotif): Given a vertex-colored temporal graph, a source, a destination, and a multiset of colors with size , decide if there exists a restless path connecting the source and the destination such that the vertex colors of the path agree with the multiset colors. • Restless reachability (RestlessReach): Given a temporal graph and a set of source vertices, find the set of vertices for which there exists a restless path connecting a source to the vertex. • Short restless reachability ( -RestlessReach): Given a temporal graph, a set of source vertices, and an integer , find the set of vertices for which there exists a restless path of length − 1 connecting a source to the vertex. • Short restless motif reachability ( -RestlessMotifReach): Given a vertex-colored temporal graph, a set of source vertices, and a multiset of colors with size , find the set of vertices for which there exists a restless path connecting a source to the vertex such that colors of vertices in the path agree with the multiset colors.

To motivate the study of restless reachability problems in temporal graphs we present three application scenarios: ( ) modeling epidemic spreading; ( ) finding signaling pathways in brain networks; and ( ) tour recommendation for travelers. Example 1. We can model the problem of estimating infections in an epidemic outbreak as a RestlessReach problem. We associate each vertex in the graph to a person and each temporal edge to a social interaction between two persons at a specific timestamp. The resting time of a vertex can be viewed as time until which the virus/disease can propagate from that vertex. After exceeding the resting time, we assume that the virus/disease becomes inactive at the vertex and/or stops propagating. Given the source of an infection, we would like to find out the set of people who may also be infected with the disease. Additionally, epidemiologists would be interested in a tool that allows them to evaluate different immunization strategies, such as, computing efficiently the spread of the disease when a selected subset of the population has been immunized to the disease, e.g., vaccinated or quarantined.

Example 2. Another application of restless reachability is to find signaling pathways in brain networks. Here we assume that brain regions are represented as vertices, and edges between the regions represent physical proximity, for example, two regions that are physically next to each other or having high signal correlation in an electro-encephalogram (EEG) are connected with an edge. Using functional magnetic resonance imaging (fmri) we can record the active brain regions at different timestamps -the frequency of the scans is approximately one second [51, 73] . We introduce a timestamp on an edge if two regions with a static edge are active in consecutive fmri scans. Finally, we introduce resting time for each region: any incoming signal can be forwarded to another region with in the resting time duration. Given the source of signal origin we would like to find all the regions to which the signal was successfully transmitted. The problem can be abstracted as a RestlessReach problem.

Example 3. Consider a tour recommendation scenario where a traveler is interested in visiting a set of places such as a historic museum, an art gallery, a café, or other. However each location has a maximum time-limit that the traveler is willing to spend. Given a start and an end location we would like to find a travel itinerary satisfying the constraints specified by the traveler. This problem can be modeled as a -RestlessMotif problem, where each location can be considered as a vertex, the color associated with the vertex represent the type of a location, for example, museum, art gallery, etc., the temporal edges between the vertices represent the transportation links, and the resting time duration associated with each vertex represents the maximum time a traveler is willing to spend at a location.

All problems considered in this work are NP-hard and as such it is likely that they admit no polynomial-time algorithm. In such cases, it is typical to resort to heuristics or approximation algorithms which still run in reasonable time but compromise the quality of the solution. In contrast, we consider exact algorithms for solving restless reachability problems in both temporal and vertex-colored temporal graphs. To also ensure fast runtime, our algorithms are exponential in the length of the path sought. More precisely, we show that when the path length is small enough our solution scales to massive graphs with up to one billion temporal edges.

To further motivate our approach, we note that Casteigts et al. [17] studied the RestlessPath problem from a complexity-theoretic point of view. For instance, they proved that the problem remains NP-hard on highly structured graphs such as complete graphs with exactly one edge removed. Despite several negative results, the authors pinpoint two parameters, say , for which the problem admits an algorithm running in time ( ) (1) , where ( ) is some computable function depending solely on the parameter . Namely, these parameters are the feedback edge number (FEN) and the timed feedback vertex number (TFVN). For the latter, the algorithm they describe runs roughly in time 6 ! (1) , where is the TVFN of the input -vertex temporal graph. 1 In order for these algorithms to be scalable, 2 the corresponding parameter values should be small in practice on relevant instances. Unfortunately, as we show in Section 6.2, this is not the case. Therefore, it appears that the only known parameterized algorithm for the problem that has hope of being fast in practice is one that pushes the unavoidable exponential dependency into the length of the path.

Our key contributions in this paper are as follows:

• We present a generating function for generating restless walks, and an algorithm based on constrained multilinear sieving [11] for solving -RestlessMotif and -RestlessMotifReach in time (2 Δ) and ( ) space, where is the number of vertices, is the number of edges, is the maximum timestamp, − 1 is the path length, and Δ is the maximum resting time. Furthermore, we show that our algorithm solves -RestlessPath and -RestlessReach in (2 Δ) time using ( ) space. For the discussion to follow, we call this algorithm a decision oracle as it merely returns a yes/no answer with no explicit solution.

• We develop the decision oracle into a fine-grained decision oracle capable of reporting the set of vertices that are reachable via a restless path from given source vertices along with the set of timestamps at which the vertices are reachable. Further, we exploit this to extract optimal solutions (i.e., solutions in which the maximum timestamp on the restless path is minimized) for -RestlessMotif and -RestlessPath. Notably, our solution improves upon the earlier work of Thejaswi et al. [71, 72] by reducing the number of queries by a factor of log . Further, for extracting a solution, we reduce the number of queries from the work of Björklund et al. [10] from ( log ) to . In total, our extraction algorithm runs in (2 Δ) time.

• As a consequence of our fine-grained decision oracle, our algorithm can answer more detailed queries. In particular, it can answer whether a given vertex is reachable from source at timestamp with a restless path of length ℓ. Such a fine-grained oracle can be used to solve multiple variants of the restless path problem, such as finding a restless path that minimizes the path length, the arrival time, or the total resting time. Another key strength of our algorithm is its adaptability to multiple variants of the restless path problem. For instance, the algorithm is not limited to a single source, but can be extended to include multiple source vertices. • We prove that our algorithms for -RestlessMotif and -RestlessMotifReach are optimal under plausible complexity-theoretic assumptions. More precisely, we prove that there exists no * ((2 − ) )-time algorithm 3 for -RestlessMotif or -RestlessMotifReach for any > 0, assuming the so-called Set Cover Conjecture [23] (see Subsection 5.10 for a precise definition). 1 In the field of parameterized algorithms, when devising algorithms for NP-hard problems, it is not unusual to ignore the exact form of any polynomial factors in the runtime and concentrate on the likely unavoidable exponential dependency on the parameter under consideration. That is, when the exact polynomial factor of the algorithm is not worked out (or omitted as non-essential) it is often represented as merely | | (1) meaning | | for some ≥ 1, where is the input and | | is its size. 2 As the problem is NP-hard, the function ( ) is necessarily exponential unless P = NP. 3 The notation * hides the factors polynomially bounded in the input size.

• With an open-source implementation we demonstrate that our algorithm scales to graphs with up to ten million edges on a commodity desktop equipped with an 4-core Haswell CPU. When scaled to a computing server with 2 × 12-core Haswell CPU, the algorithm scales to graphs with up to one billion temporal edges [70] . As a case study, we model disease spreading in social gatherings as a -RestlessReach problem and perform experiments to study the propagation of the disease using the co-presence datasets from socio-patterns [31] . We also perform experiments to check the change in the disease spreading pattern with the presence of people with immunity.

The rest of this paper is organized as follows. In Section 2 we review the related work and put our approach in perspective. We introduce the necessary notation in Section 3 and we formally define the reachability problems for temporal graphs and vertex-colored temporal graphs in Section 4. Afterwards, our algorithmic solution is presented in Section 5. Our empirical evaluation on a large collection of synthetic and real-world graphs is discussed in Section 6, and finally, Section 7 offers a short conclusion and directions for future work.

In this section we report the research which is relevant to our work.

Static graphs. Graph reachability in static graphs is the problem of verifying if there exists a path between a pair of vertices. Fundamental algorithms like breadth first search (bfs) solve the problem in linear time. Alternatively, we can precompute the answer for each possible vertex pair by an all-pairs shortest path algorithm, after which each query can be answered in constant time. However, for large graphs with the number of vertices in the billions both approaches are problematic though with different trade-offs. First, linear time achieved by bfs can be too slow in practice though its memory requirements are manageable. Second, to achieve constant-time queries, the memory trade-off is prohibitive as there are roughly 2 pairs of vertices to consider. As such, more scalable techniques seek to find a small representation of the input graph, and exploit the transitive-closure property or index construction techniques such as tree cover, chain cover, 2-hop, 3-hop and landmark based indexing to reduce the running time and memory requirements [1, 18, 20, 43, 69, 74] . For more details, we refer the reader to the survey of Yu and Cheng [84] .

Temporal graphs. Path problems in temporal graphs are well-studied within different communities, including algorithms, data mining, and complex networks. The problem variants that seek to find a path that minimizes different objectives such as path length, arrival time, or duration, as well as finding top-shortest temporal paths are solvable in polynomial time [32, 34, 80, 81, 83] . In recent years, there has been an emphasis on more expressive temporal path problems due to their applicability in various fields [3, 15, 64, 77] .

The problem of finding a temporal path under waiting time restrictions was introduced by Dean [26] , who studied a polynomial-time solvable variant of the problem. More recently, Casteigts et al. [17] proved that RestlessPath is NP-hard and also that -RestlessPath is W[1]-hard parameterized by either the feedback vertex number or the pathwidth of the input graph. Himmel et al. [35] considered the restless walk problem where several visits to a vertex are allowed and presented polynomial-time algorithms. Estimating reachability with waiting-time constraints has been studied by Badie-Modiri et al. [4] . The complexity of finding small separators that separate two given vertices in a temporal graph was studied by Zschoche et al. [88] . Furthermore, Fluschnik et al. [30] used temporal separators to classify temporal graphs. Network reachability in temporal graphs without waiting time restrictions has been studied and a practical implementation that can scale to graphs with up to tens of thousands of vertices was presented by Holme [36] . The author studied a variant of the problem that reports connectivity between all pairs of vertices, whereas our work considers reachability from a set of sources to the other vertices in the graph. Sengupta et al. [68] presented approximation techniques based on random walks to estimate reachability in both static and temporal graphs.

Constrained graph reachability. Constrained path problems ask us to find a path between a pair of vertices with additional constraints imposed on the path. For instance, a solution path can be restricted to avoid a subset of vertices and/or forced to visit a subset of vertices. In vertex-weighed graphs, some constrained path problems try to optimize the length of the path while restricting the total weight on vertices to a budget, these problem variants are known to be NP-hard (see the work of Festa [29] or Irnich and Desaulniers [38, Chapter 2] ). Here, the length of the path is defined as the number of edges in the path. Note that, the set of vertices and edges can be interchanged by constructing the line graph of the input graph with only a polynomial increase in the graph size. Thus, most algorithms for vertex-labeled graphs can be applied to solve the corresponding edge-labeled problem variants and vice versa. For related work, we refer the reader to the work of Festa [29] .

Wang et al. [78] and Yuan et al. [85] studied constrained path problems in timedependent graphs i.e., the travel time of edges varies over time. Yuan et al. [85] show that computing a constrained shortest path over a time interval in time-dependent graphs is EXPSPACE-hard and present heuristics to solve the problem.

A basic question in edge-labeled static graphs is to verify if a pair of vertices is reachable using only edges which correspond to a subset of labels. This problem is solvable in polynomial time by filtering the input graph to contain only edges corresponding to the subset of labels under consideration. As such, a path between two vertices is obtained by bfs. However, answering such queries for all subsets of the label set has an exponential dependency on the number of labels. Many approaches including transitive closure, tree cover, 2-hop cover, and landmark indexing strategies used to verify reachability have been extended to solve label-constrained reachability problems [14, 42, 59, 60] . For instance, Peng et al. [60] show that a 2-hop indexing approach scales to graphs with 68 million nodes and 2.5 billion edges when the number of labels is at most eight.

Epidemic modeling. Due to epidemic outbreaks ranging from sars, mers, and Ebola to most recently covid-19, there has been considerable interest in studying diseasespreading models. Indeed, human-contact networks can be modeled as temporal graphs, which preserve the network dynamics with respect to time, thus, abstracting the analysis of the epidemic outbreaks as fundamental problems in temporal graphs [27, 58, 63] . For instance, Rozenshtein et al. [64] modeled the problem of reconstructing the epidemic spreading with partial information as a Steiner tree problem in temporal graphs. Additionally, the problem of identifying potential pathways of disease transmission has been successfully modeled using temporal graphs [3, 28] . Epidemic outbreaks can be modeled as diffusion processes in temporal and dynamic graphs. Likewise, many models used to study information diffusion, information cascades and marketing recommendations in social media can be adapted to solve related problems in epidemic modeling [41, 62, 76, 86] . Finding effective immunization strategies has been an important area of research due to its real-world impact in minimizing the scale of an epidemic outbreak and the problem is analogous to finding a fraction of vertices in a social network to maximize the influence [46] . As such, the approaches used to solve influence maximization problems can be adapted to solve the problem of outbreak minimization [19] . To summarize, these approaches provide us a way to understand the disease propagation in epidemic outbreaks [28] , the transmission of diseases across generations [3] , as well as immunization strategies that are effective to minimize the scale of epidemic outbreaks [62, 63] .

Multilinear sieving. Algebraic algorithms based on multilinear sieving for solving path problems in static graphs are due to Koutis and Williams [47, 48, 79] . Björklund et al. [7] improved the technique using narrow sieves to get a breakthrough result for the Hamiltonian path problem by showing that it admits an algorithm running in * (1.66 ) time. The sieving technique was extended to find trees and connected subgraphs by Björklund et al. [11] , who generalized the approach using a constrained variant of the sieve to find paths and subgraphs that agree with a multiset of colors. A practical implementation of the sieve was provided by Björklund et al. [12] . Furthermore, its parallelizability to vector-parallel architectures and scalability to large subgraph sizes was shown by Kaski et al. [45] . Note that these algorithms only handle static graphs. More recently, Thejaswi et al. [71] extended the sieving technique to solve a family of pattern-detection problems in temporal graphs. They also presented a vertex-localized variant of the sieve and a memory-efficient implementation scaling to temporal graphs with one billion edges [72] .

Recent advancements. The RestlessReach and -RestlessReach problems that we study in this paper generalize the problems of RestlessPath and -RestlessPath problems, respectively. The latter problems, which ask for the existence of a restless path between a source and a destination, are studied by Casteigts et al. [17] , who established their NP-hardness and developed fixed-parameter tractable algorithms. More recently, the authors presented algorithms with running time (2 (1) ) and (2 (1) ) for the -RestlessPath and RestlessPath problems, respectively, where is the number of vertices in the input temporal graph and the length of the path. It should be noted that their algorithm only reports the existence of a restless path between a source and a destination with a yes/no answer but does not return an explicit solution. In many practical scenarios, such as where further analysis of the path is required, this is insufficient.

In comparison to the work of Casteigts et al. [17] , our approach can detect and extract an optimal (i.e., one minimizing the maximum timestamp) restless temporal path in time (2 Δ) and (2 Δ) for the -RestlessPath and RestlessPath problems, respectively, where is the number of vertices, is number of temporal edges, and Δ is the maximum resting time. Furthermore, our method can be used to answer reachability queries, i.e., finding the set of vertices that are reachable from a set of sources, in a single computation and without having to iterate over each vertex. In addition, our method solves a general variant of the restless path problem with color constraints on the vertices.

In this section we introduce our notation and basic terminology. A list of symbols used in this paper is available in Table 7 .

Static graphs. A (static) undirected graph is a tuple ( , ) where is a set of vertices and is a set of unordered pairs of vertices called edges. A (static) directed graph is a tuple ( , ) where is a set of vertices and is a set of ordered pair of vertices called edges. A (static) walk between any two vertices is an alternating sequence of vertices and edges 1 1 2 . . . such that there exists an edge = ( , +1 ) ∈ for each ∈ [ − 1]. 4 We call the vertices 1 and the start and end vertices of the walk, respectively. We refer to walk as ( , )-walk for 1 = and = . The length of a static walk is the number of edges in the walk. A (static) path is a static walk with no repetition of vertices.

Undirected temporal graphs. An undirected temporal graph is a tuple ( , ), where is a set of vertices and is a set of undirected temporal edges. An undirected temporal edge is a tuple ( , , ) where , ∈ and ∈ [ ] is a timestamp, where is the maximum timestamp in . Note that, by definition, two undirected edges ( , , ) and ( , , ) are equivalent. A vertex is adjacent to vertex and vice versa at timestamp in an undirected graph if there exists an undirected edge ( , , ) ∈ . A temporal walk is an alternating sequence of vertices and temporal edges 1 1 2 2 . . . −1 such that ∈ for all ∈ [ − 1] and for any two edges = ( , +1 , ), +1 = ( +1 , +2 , +1 ) in , it is ≤ +1 . We say the walk reaches vertex at time −1 . The vertices 1 and are called source and destination vertices of , respectively. The vertices { 2 , . . . , −1 } are called in-vertices (or equivalently, internal vertices) of . We refer to the temporal walk as ( , )-temporal walk with source = 1 and destination = . The vertex set and edge set of walk is denoted as ( ) and

( ), respectively. The length of a temporal walk is the number of edges in the temporal walk. A temporal path is a temporal walk with no repetition of vertices. Unless stated otherwise, by a temporal graph we always mean a directed temporal graph. Similarly, by a temporal walk we always mean a directed temporal walk, and by a temporal path we always mean a directed temporal path. To distinguish a temporal graph from a static graph, we sometimes explicitly call a graph non-temporal or static.

Restless walk. A restless temporal walk, or simply restless walk, is a temporal walk such that for any two consecutive edges = ( , +1 , ) and +1 = ( +1 , +2 , +1 ), it holds that +1 − ≤ ( +1 ), where the function : → [Δ] defines a vertexdependent waiting time, with Δ ∈ N + being the maximum waiting time. In other words, in a restless temporal walk, it is not allowed to wait more than a vertex-dependent amount of time in each vertex. A restless path is a restless walk with no repetition of vertices.

Coloring. Let to be a set of colors. A vertex-colored temporal graph = ( , ) is a temporal graph with a vertex-coloring function : → , which maps each vertex ∈ to a subset of colors in . Let be a multiset of colors and be a walk. The walk is properly colored (or is said to agree with ) if there exists a bijective mapping : ( ) → such that ( ) ∩ ( ) ≠ ∅ for all ∈ ( ).

Polynomials. We assume that our temporal graph contains vertices and temporal edges, and for simplicity we write = { 1 , . . . , } and = { 1 , . . . , }. We introduce a variable for each ∈ and a variable for each ∈ . Let be a multivariate polynomial such that each monomial P ∈ is of the form 1 1 . . . is properly colored if for each ∈ it holds that ( ) = ∈ −1 ( ) , in other words, the number of occurrences of color is equal to the total degree of -variables representing the vertices with color .

In this section we define the problems that we consider in this paper. While we define the problems on temporal directed graphs, we note that our algorithmic approach can be extended to undirected graphs by replacing each undirected edge with two directed edges in opposite directions. In such case, the asymptotic complexity of the algorithm remains the same.

Restless path problem (RestlessPath). Given a temporal graph = ( , ), a function : → N + , a source ∈ , and a destination ∈ , the problem asks if there exists a restless path from to in .

Short restless path problem ( -RestlessPath). Given a temporal graph = ( , ), a function : → N + , a source ∈ , a destination ∈ , and an integer ≤ , the problem asks if there exists a restless path of length − 1 from to in .

Short restless motif problem ( -RestlessMotif). Given a temporal graph = ( , ) with a coloring function :

→ where is a set of colors, a function : → N + , a source ∈ , a destination ∈ , and a multiset of colors, | | = , the problem asks if there exists a restless path from to in such that the vertex colors of the path agree with .

An illustration of restless path problems is available in Figure 1 .

All these three problems are NP-hard (the hardness of the first two can be found in the paper of Casteigts et al. [17] ). For the last claim, observe that the -RestlessPath problem is a special case of the -RestlessMotif problem where all the vertices in the graph are colored with a single color and the query multiset is = {1 }. Since -RestlessPath is NP-hard, it follows that -RestlessMotif is NP-hard, as well.

Restless reachability problem (RestlessReach). Given a temporal graph = ( , ), a function : → N + , and a source vertex ∈ , the problem asks to find the set of vertices ⊆ such that for each ∈ there exists a restless path from to in . Clearly, the problem generalizes RestlessPath and is thus computationally hard. Short restless reachability problem ( -RestlessReach). Given a temporal graph = ( , ), a function : → N + , a source vertex ∈ , and an integer ≤ , the problem asks to find the set of vertices ⊆ such that for each ∈ there exists a restless path of length − 1 from to in . Given that -RestlessPath is hard, -RestlessReach remains hard, as well. Short restless motif reachability problem ( -RestlessMotifReach). Given a temporal graph = ( , ) with coloring function : → where is a set of colors, a function : → N + , and a multiset of colors such that | | = , the problem asks to find the set of vertices ⊆ such that for each ∈ there exists a restless path from and in such that the vertex colors of the path agree with multiset . Again, a routine observation shows that this problem is computationally hard.

An illustration of restless reachability problems is presented in Figure 2 .

Our approach makes use of the polynomial encoding of temporal walks introduced by Thejaswi et al. [71] , building on the earlier work of Björklund et al. [11] for static graphs. Because algebraic fingerprinting techniques are not well-known, we first provide some intuition behind our methods before diving into details.

Algebraic fingerprinting methods have been successfully applied to pattern detection problems on graphs. On a high level, the approach works by encoding a problem instance as a multivariate polynomial where the variables in the polynomial correspond to entities of such as a vertex or an edge. The key idea is to design a polynomial encoding, which evaluates to a non-zero term if and only if the desired pattern is present in . We can then evaluate the polynomial by substituting random values to its variables. Now, if one of the substitution evaluates to a non-zero term, it implies that the desired pattern is present in . Since the substitutions are random, the 

Arrows represent the direction of edges and the integer value on each edge corresponds to its timestamp. On the left, an example of a restless path from 1 to 6 of length 5. On the center, an example of a restless path from 1 to 6 when the length of the path is restricted to 4 i.e., = 5. On the right, an example of a short restless (path) motif from 1 to 6 such that the vertex colors of the path agree with the multiset of colors in . Restless paths are highlighted in bold (blue). Restless reachability Short restless reachability Short restless motif reachability . . , 9 } with source = 1 and resting time of vertices ( 1 ) = · · · = ( 9 ) = 2. Arrows represent the direction of edges and the integer value on each edge correspond to its timestamp. On the left, an example of restless reachability where vertices of except for 5 , highlighted in red, are reachable from source = 1 via a restless path. On the center, an example of short restless reachability when the length of the path is restricted to 2 i.e., = 3, only 4 and 6 are reachable from via restless path of length 2. On the right, an example of short restless motif reachability such that the vertex colors of the path agree with the multiset of colors in . Only 9 is reachable from via a restless path agreeing multiset of colors in . approach can give false negatives. However, the resulting algorithms typically have one-sided error meaning false positives are not possible. Moreover, as is typical, the error probability can be made arbitrarily small (e.g., as unlikely as hardware failure) by repeating the substitutions.

In our case we need to decide the existence of a restless path in a temporal graph . Following the approach presented above, we encode all the restless walks in using a multivariate polynomial where each monomial corresponds to a restless walk and variables in a monomial correspond to vertices and/or edges. Specifically, we design an encoding where a monomial is multilinear (i.e., no variables in the monomial are repeated) if and only the corresponding restless walk it encodes is a restless path.

As such, the problem of deciding the existence of a restless path is equivalent to the problem of deciding the existence of a multilinear monomial in the generated polynomial. The existence of a multilinear monomial in a polynomial, in turn, can be determined using polynomial identity testing, in particular, by evaluating random substitutions for the variables; if one of the substitution evaluates to a non-zero term then there exists at least one multilinear monomial in the polynomial. Importantly, note that an explicit representation of the polynomial encoding can be exponentially large. However, in our approach we do not need to represent the polynomial explicitly, but we only need to evaluate random substitutions efficiently.

To lay foundation for our approach we begin our discussion with encoding walks in static graphs and continue to encode walks in temporal graphs. Finally, we extend the approach to encode restless walks in temporal graphs.

Static graphs. We introduce a set of variables ì = { 1 , . . . , } for vertices in = { 1 , . . . , } and a set of variables ì = { ,ℓ : ( , ) ∈ , ℓ ∈ [ ]} such that ,ℓ corresponds to an edge ( , ) ∈ that appears at position ℓ in a walk. Using these variables a walk = 1 1 2 . . . −1 can be encoded by the monomial

The monomial encoding of walks in static graphs is illustrated in Figure 3 . It is easy to see that the encoding is multilinear, i.e., no variable in a monomial is repeated, if and only if the corresponding walk is a path. To encode a walk of length − 1, we need variables of x and − 1 variables of y, for a total of 2 − 1 variables.

Temporal graphs. We introduce a set of variables ì = { 1 , . . . , } for vertices = { 1 , . . . , } and a set of variables ì = { ,ℓ, : ( , , ) ∈ , ℓ ∈ [ ]} such that ,ℓ, corresponds to an edge ( , , ) ∈ that appears at position ℓ in a walk. Using these variables a temporal walk = 1 1 2 . . . −1 can be encoded using the monomial

The polynomial encoding of temporal walks is illustrated in Figure 4 . A monomial encoding of a temporal walk of length − 1 has 2 − 1 variables. Again, observe that the encoding is multilinear if and only if the corresponding temporal walk is a temporal path. In fact, it can be shown that a temporal walk is a temporal path if and only if the corresponding monomial encoding is multilinear [71, Lemma 2] . Likewise, the problem of deciding the existence of temporal path of length − 1 is equivalent to deciding the existence of a multilinear monomial of degree 2 − 1 [71, Lemma 3] . In other words, if we encode all the walks of length − 1 in a temporal graph using a polynomial where each monomial encodes a walk, then the problem of detecting the existence of a temporal path of length − 1 is equivalent to the problem of detecting existence of a multilinear monomial of degree 2 − 1 in the encoded polynomial.

To generate a polynomial encoding of temporal walks, we turn to a dynamic-programming recursion. That is, we make use of polynomial encoding of temporal walks of length ℓ − 2 to generate the encoding of temporal walks of length ℓ − 1 recursively.

Consider the example illustrated in Figure 5 , where the vertex has incoming edges from vertices { 1 , 2 } at timestamp , i.e., ( ) = { 1 , 2 }. Let ,ℓ, ( ì, ì) denote the polynomial encoding of all temporal walks of length ℓ − 1 ending at vertex at latest time . Following our notation, 1 ,ℓ−1, ( ì, ì), 2 ,ℓ−1, ( ì, ì) represent the polynomial encoding of walks ending at vertices 1 , 2 , respectively, such that all walks have length ℓ − 1 and end at latest time . From the definition of a temporal walk, it is clear that we can walk from vertices 1 , 2 to vertex at time if we have reached 1 and/or 2 at latest time . The polynomial encoding of walks of length ℓ − 1 ending at vertex at latest time can be written as

By generalizing the above intuition, a generating polynomial for temporal walks can be written as 

for each ∈ , ℓ ∈ {2, . . . , } and ∈ [ ]. An illustration of polynomial encoding of temporal walks is presented in Figure 6 , in which we depict the polynomial encoding of temporal walks of length zero (a, b), length one (c, d) and length two (e, f).

Before continuing to introduce a generating function for restless walks let us present an overview of the algorithm.

To obtain our algorithm, we proceed by taking the following steps. First, we present a dynamic programming algorithm to encode restless walks as a polynomial and from this polynomial, show that detecting a multilinear monomial of degree 2ℓ − 1 is equivalent to detecting a restless path of length ℓ − 1, and vice versa. Then, we extend the approach to detecting restless paths with additional color constraints on the vertices. Finally, we use this algorithm to solve the problems described in Section 4.

In this work we use finite fields for evaluating polynomials, in particular we make use of Galois fields (GF) of characteristic 2. An element of GF(2 ) can be represented as a bit vector of length . We can perform field operations such as addition and multiplication on these bit vectors in time ( log ) [54] . The polynomial ,ℓ, ( ì, ì) on variables ì = { : ∈ }, ì = ,ℓ, : ( , , ) ∈ , ℓ ∈ [ ] in Equation (1) can be evaluated using a random assignment˜= {˜∈ GF(2 )} :

∈ ì},˜= ˜, ℓ, ∈ GF(2 ) :

,ℓ, ∈ ì . Now we can build an arithmetic circuit that represents an algorithm which evaluates the polynomial ,ℓ, for input (˜,˜) in time linear in the number of gates in the circuit. Most importantly, observe that the expanded expression of the polynomial ,ℓ, ( ì, ì) can be exponentially large, however the arithmetic circuit evaluating ,ℓ, ( ì, ì) can be reduced to size polynomial in number of gates by applying the associativity of addition and distributivity of multiplication over addition.

For detecting the existence of a multilinear monomial in the generated polynomial, the algorithm works by randomly substituting values (˜,˜) ∈ GF(2 ), for a suitable , to variables in ì = { : ∈ } and ì = ,ℓ, : ( , , ) ∈ , ℓ ∈ [ ] . Specifically, the parameter is the number of bits used to generate the field variables. Because multiplication between two field variables is defined as an XOR operation, multiplication between two variables with the same value results in a zero term. That is, the monomials corresponding to walks that are not paths evaluate to a zero term, while the monomials corresponding to paths evaluate to a non-zero term. However, it is possible that an evaluation results in a zero term even though there is a multilinear monomial term corresponding to a path. To eliminate the effect of such false negatives we repeat 

6. An illustration of polynomial encoding of temporal walks of length zero (a,b), length one (c, d), and length two (e, f). Arrows denote direction of edges and numbers on edges denote edge timestamps. Observe that the monomial encoding corresponding to a walk that is not a path is not multilinear (highlighted in red).

the evaluation of the polynomial with 2 random substitutions. The probability of a false negative then becomes 2 − (2 − 1), where − 1 is the length of the temporal walk. In practice, the false negative probability depends on the quality of the random number generator. It is important to note, however, that the false positive probability is zero. For full technical details, we refer the interested reader to Björklund et al. [11] and Cygan et al. [24, Chapter 10] .

In this subsection we extend the dynamic-programming recursion to generate a polynomial encoding of restless walks of length ℓ − 1 using encoding of restless walks of length ℓ − 2.

An example is illustrated in Figure 7 , in which we depict a vertex with incoming neighbors ( ) = { 1 , 2 }. From the definition of a restless walk, it is clear that we can continue the walk from vertices 1 , 2 to vertex at time only if we had reached 1 or 2 no earlier than time − ( 1 ) and − ( 2 ), respectively. Let ,ℓ, ( ì, ì) denote the encoding of all restless walks of length ℓ − 1 ending at vertex at time . We generate restless walks of length ℓ − 1 that end at vertex at time using restless walks of length ℓ − 2 by having

Generalizing from the previous example, the dynamic-programming recursion is written as ,1, ( ì, ì) = , for each ∈ and ∈ [ ], and

The following result is fundamental to our approach.

Lemma 5.1. The polynomial encoding ,ℓ, ( ì, ì) presented in Equation (2) contains a multilinear monomial of degree 2ℓ − 1 if and only if there exists a restless temporal path of length ℓ − 1 ending at vertex reaching at time . (2) it is clear that if the -variables are not repeated in a monomial, the walk ends at vertex and has length ℓ − 1. Let us assume that the polynomial has a multilinear monomial with degree 2ℓ − 1. It is easy to see that the variables of this monomial are different, so the walk represented by the monomial is a path. From the construction it is also clear that we only continue the walk if we have reached the neighbor at time at least − ( ). Conversely, let us assume that there exists a restless path of length ℓ − 1 that ends at vertex at latest time . Since the length of the path is ℓ − 1, there are ℓ unique -terms and ℓ − 1 unique -terms, and thus, there exists a multilinear monomial of degree 2ℓ − 1. □ The next part of the problem is to detect a multilinear monomial in the polynomial in Equation (2) representing the restless walks. There is already established theory related to this problem [11, 47, 48] . In particular, it is known that by substituting 2 ℓ random values for the variables in and , and evaluating them, if one of the evaluation results in a non-zero term, it implies that there exists at least one multilinear monomial of degree 2ℓ − 1.

For each ∈ and ∈ [ℓ] we introduce a new variable , . The vector of all variables of , is denoted as z and the vector of all variables of is denoted as y. We write = ∈ , , for ∈ , ⊆ [ℓ] and z = { : ∈ } for ⊆ [ℓ] . The values of the variables , are assigned uniformly at random from GF (2 ) . For simplicity we write = { 1 , . . . , }.

Lemma 5.2 (Multilinear sieving [9] ). The polynomial

is not identically zero if and only if ,ℓ, ( ì, ì) contain a multilinear monomial of degree 2ℓ − 1.

Lemma 5.3. Evaluating the polynomial in Equation (3) can be done in time (2 ℓ ℓ Δ) and space ( ).

is the number of edges at ∈ [ ], and is the number of vertices. Computing , , ( ì, ì) for all ∈ requires (Δ + 1) multiplications and additions. We repeat this for all ∈ [ ] and ∈ [ℓ], which requires (ℓ Δ) multiplications and additions. Finally we evaluate the polynomial ,ℓ, (ì, ì) for all ∈ using 2 ℓ random substitution of variables in z = { 1 , . . . , }, for each ⊆ [ℓ], which takes time (2 ℓ ℓ Δ). So the runtime is (2 ℓ Δ). To store ,ℓ, ( ì, ì), for all ∈ , ∈ [ ], requires at most ( ) space. The dynamic-programming scheme iterates over ∈ [ℓ] for computing ,ℓ+1, ( ì, ì), which requires the values of ,ℓ, ( ì, ì), for all ∈ , ∈ [ ]. It follows that the space requirement is ( ). □

In the next subsection, we introduce color constraints for the vertices in the restless path. More precisely, given a vertex-colored temporal graph = ( , ) with a coloring function : → , where is a set of colors, and a multiset of colors, we consider the problem of deciding the existence of a restless path such that the vertex colors of the path agree with the multiset of colors in . This generalization of the restless path problem with color constraints will be used to solve restless reachability problems in the later sections.

Given a multiset of colors , we extend the multilinear sieving technique to detect the existence of a multilinear monomial, such that colors corresponding to the -variables agree with the colors in multiset .

Recall our earlier definition where ( ) denotes the number of occurrences of color in a multiset . Furthermore, for each ∈ , let denote the set of ( ) shades of the color , with ∩ ′ = ∅ for all ≠ ′ . In other words, for each color ∈ we create ( ) shades, so that any two distinct colors have different shades. As an example, for the color multiset = {1, 1, 2} we have 1 

For each ∈ and ∈ ( ) we introduce a new variable , . For each ∈ ∪ ∈ and each label ∈ [ℓ] we introduce a new variable , . The values of variables , and , are drawn uniformly at random from the Galois field GF(2 ). We write

for ⊆ [ℓ], ∈ . The following lemma extends Lemma 5.2 in the case of vertex-color constraints.

Lemma 5.4 (Constrained multilinear sieving [11] ). The polynomial ,ℓ, ( ì, ì) contain a multilinear monomial of degree 2ℓ − 1 and it is properly colored if and only if the polynomial

is not identically zero.

From Lemma 5.4, we can determine the existence of a multilinear monomial in ,ℓ, (ì, ì, ì), by making 2 ℓ random substitutions of the new variables z in Equation 5. As detailed in Björklund et al. [11] these substitutions can be random for a lowdegree polynomial that is not identically zero with only few roots. If one evaluates the polynomial at a random point, one is likely to witness that it is not identically zero [66, 87] . This gives rise to a randomized algorithm with a false negative probability of 2 − (2ℓ − 1), where the arithmetic is over the Galois field GF(2 ). Here, again, is the number of bits used to generate the random values. We make use of this result for designing our algorithms. Lemma 5.5. Evaluating the polynomial in Equation (5) can be done in time (2 ℓ ℓ Δ) and space ( ).

The proof of Lemma 5.5 is similar to the one of Lemma 5.3. From Lemma 5.4 we obtain an algorithm to detect the existence of a restless path ending at vertex ∈ at time and the vertex colors of the restless path agree with the colors in multiset .

In this subsection we present a fine-grained evaluation scheme to evaluate the polynomial in Equation (5). Intuition. Consider the graph illustrated in Figure 8 , with vertex set = { 1 , . . . , 5 } with resting time ( 1 ) = · · · = ( 5 ) = 2, i.e., we can wait at most 2 time steps at any 

vertex. In order to decide whether there exists a restless path of length 3 (i.e., ℓ = 4) in the graph, we need to evaluate the polynomial ( ì, ì) =

,4, ( ì, ì). However, to decide if there exists a restless path of length 3 ending at vertex 5 it is sufficient to evaluate the polynomial ∈ [ ] 5 ,4, ( ì, ì). Furthermore, to decide if there exists a restless path of length 3 ending at vertex 5 at time 5, we can restrict the evaluation to the polynomial 5 ,4,5 ( ì, ì). Similarly, it suffices to evaluate the polynomial ,ℓ, ( ì, ì) to determine whether there exists a path of length ℓ − 1 ending at vertex at time .

Fine-grained decision oracle. Let us generalize the fine-grained evaluation scheme to any temporal graph using the intuition presented. Instead of evaluating a single polynomial (x, y) =

,ℓ, ( ì, ì), we work with a set of polynomials ,ℓ, ( ì, ì) : ∈ , ∈ [ ] and evaluate each ,ℓ, ( ì, ì) independently. Observe carefully that our generating function in Equation (2) generates a polynomial encoding of all restless walks ,ℓ, ( ì, ì) for each ∈ and ∈ [ ] independently for a fixed ℓ. If the corresponding evaluation polynomial ,ℓ, (ì, ì, ì) evaluates to a non-zero term, it implies that there exists a restless path of length ℓ − 1 ending at vertex at time and the vertices in the path agree with the multiset of colors in . Using this fine-grained evaluation scheme, we obtain a set of timestamps = { : ,ℓ, (ì, ì, ì) ≠ 0 for all ∈ [ ]} of restless paths ending at vertex ∈ and satisfying the color constraints in . The pseudocode is presented in Algorithm 1.

The term fine-grained oracle is used to differentiate it from a decision oracle, which only reports the existence of a restless path with a YES/NO answer. Our fine-grained decision oracle reports more insightful details, for instance it can answer if there exists a restless path of length ℓ − 1 ending at vertex ∈ at time ∈ [ ] satisfying the color constraints specified in with a YES/NO answer. A single run of the fine-grained oracle is sufficient to obtain the set of vertices ⊆ such that there exists a restless path of length ℓ − 1 ending at each ∈ . Additionally, we can obtain the set of reachable timestamps = { : , = 1, ∈ [ ]} for each ∈ using a single query to the fine-grained oracle.

This re-design of the polynomial evaluation scheme improves the runtime for solving the temporal path problems described in previous work [71, 72] , where the authors search for a temporal path that contains colors specified in the query. That is, by replacing their decision oracle with our fine-grained decision oracle, we reduce the number of queries by a factor of log . This, in turn, reduces the total runtime of their solution for detecting an optimal solution from (2 ℓ ℓ ( + ) log ) to (2 ℓ ℓ ( + )). Even though the theoretical improvement is modest, it is important to note that for large values of ℓ a single run of the decision oracle can take hours to complete, so the practical improvement is significant (for precise results, see Section 6 and Table 5 , as well as previous work [45] ).

Let us then turn to our algorithmic results. Oracle with instance ( ′ , ′ , + 1, ′ ). The construction is depicted in Figure 9 . In the instance ( ′ , ′ , + 1, ′ ), the origin of the graph is enforced by introducing an additional vertex ′ adjacent to . Since ′ is assigned a unique color, if there is a resting path agreeing with ′ , then the path must originate from ′ and pass through . If there exists a restless path originating from ′ and ending at ∈ \ { , ′ } such that the vertex colors of the path agree with ′ , then we have a restless path originating from and ending at such that the vertex colors of the path agree with . As the graph ′ will have at most 2 edges and + 1 vertices, we have obtained an algorithm for solving -RestlessMotifReach using (2 Δ) time and ( ) space. □ Next, we present our algorithm for -RestlessReach obtained by transforming it to an instance of -RestlessMotifReach. More precisely, the algorithm works by constructing a vertex-colored instance that encodes the source, whereas a multiset of colors encodes the path length. We first present the solution for -RestlessReach with the solution to RestlessReach following as a special case.

Theorem 5.7. There exists a randomized algorithm for solving the -RestlessReach problem in time (2 Δ) and space ( ).

Proof. Given an instance ( , , ) of the -RestlessReach problem, we introduce a coloring function : → {1, 2} such that ( ) = 2 and ( ) = 1 for all ∈ \ { }. We obtain a graph ′ = ( , \ {( , , ) ∈ : = }) by removing all incoming edges to in , and by setting the multiset = {1 −1 } ∪ {2}. We query the FineGrained-Oracle with instance ( ′ , , , ). The transformation is illustrated in Figure 10 . In the instance ( ′ , , , ), the origin of the restless path is enforced by removing all incoming edges to and coloring with a unique color. If we have a restless path ending at ∈ \ { } and agreeing with multiset , it implies that the temporal path originates from and ends at . The graph ′ has + 1 vertices and edges, so we have a (2 Δ) time and ( ) space algorithm for solving -RestlessReach. □ Theorem 5.8. There exists a randomized algorithm for the RestlessReach problem in time (2 Δ) and space ( ).

Proof. For solving RestlessReach, the construction is similar to Theorem 5.7. However, we need to make − 2 calls to the FineGrainedOracle assuming the In total, we make − 2 FineGrainedOracle calls for each ∈ {2, . . . , − 1}. Each run of the oracle takes (2 Δ) time. To summarize, the runtime of the algorithm 22 is −1 =2 2 Δ, which is (2 Δ). The space complexity is ( ), completing the proof. □

Consider the following variant of the restless reachability problem that we call atmost--restless reachability problem (atm--RestlessReach). Given a temporal graph and a source vertex we need to find a set of vertices which are reachable from source via a restless path such that the length of the path is at most − 1. From Theorem 5.8, we have a randomized algorithm for solving atm--RestlessReach in time (2 Δ) and space ( ). Also note that we can use the algorithms for -RestlessMotifReach, -RestlessReach and RestlessReach as we can solve the -RestlessMotif, -RestlessPath and RestlessPath problems, respectively. A general variant of the RestlessReach problem with a set of sources ⊆ can be reduced to the RestlessReach problem with a single source by introducing an additional vertex ′ and connecting all the sources ∈ to ′ with a temporal edge. More precisely, given a graph = ( , ) and set of sources ⊆ , we construct a graph ′ = ( ′ , ′ ) with ′ = ∪{ ′ } and ′ = ∪{( ′ , , ) | ∈ and ( , , ) ∈ }. Solving the RestlessReach problem on the graph instance ′ with source ′ is equivalent to solving the RestlessReach problem with set of sources . Additionally, finding the restless path that minimizes the length (shortest path), minimizes the arrival time (fastest path), or minimizes the total waiting time (foremost path) can be computed using the output ′ : ∈ for each ℓ ∈ {2, . . . , } from the fine-grained oracle. However, enabling such computation requires ( ) space.

In this subsection, we present an algorithm for extracting an optimal solution for -RestlessMotif and -RestlessPath using queries to the FineGrainedOracle. By optimal we mean that the maximum timestamp in the restless path is minimized. Our FineGrainedOracle reports the existence of a restless path from a given source to a destination at discrete timestamps with a YES/NO answer. However, in many cases we also require an explicit solution, i.e., a restless path which actually witnesses the fact. We present two approaches to extracting an optimal solution. Our first approach makes use of self-reducibility of decision oracles and temporal DFS, based on the previous work of Björklund et al. [10] and Thejaswi et al. [72] . Our second approach makes use of the fine-grained oracle. For using self-reducibility, we implement a naive version of the multilinear sieve which only reports a YES/NO answer without the fine-grained capabilities, that is, the algorithm does not report the set of vertices and the timestamps at which the vertices are reachable from a given source via a restless path. We summarize our results in Table 1 . Using self-reducibility and temporal DFS. The approach works in three steps: First, we obtain the minimum (optimal) timestamp ∈ [ ] for which there exists a feasible solution. For this, we construct the polynomial encoding of restless walks of length − 1 which end at time at most ′ ∈ [ ] and query the decision oracle for the existence of a solution. Using binary search on the range [ ], we use at most log queries to obtain the optimal timestamp. Next, we extract a -vertex temporal subgraph that contains a restless temporal path. By recursively dividing the graph in to two halves we can obtain the desired subgraph using ( log ) queries to the decision oracle in expectation [10] . Finally, we extract the restless path by performing a temporal DFS from a given source in the -vertex subgraph. Even though the worst case complexity of the temporal DFS is ( !), we demonstrate that the approach is practical. For technical details of self-reducibility of decision oracles, we refer the interested reader to Bjorklund et al. [10] . In summary, the overall complexity of extracting an optimal solution using selfreducibility and temporal DFS is ((2 2 Δ log log ) + !). Using fine-grained oracle. As a second approach, extracting a solution can also be done with queries to the fine-grained oracle. Let us present the high-level idea behind fine-grained extraction. Consider a temporal graph presented in Figure 11 with vertex set = { 1 , . . . , 6 } with resting times ( 1 ) = · · · = ( 6 ) = 2. In this example we want to extract a restless path of length 3 from vertex 1 to vertex 6 , if such a restless path exists. For illustrative purposes, we use colors black and red and have the multiset of colors = { , , , }. For the first iteration it suffices to verify if 6 ,4, (ì, ì, ì) evaluates to a non-zero term for each ∈ [ ]. Since there exists a restless path of length 3 ending at vertex 6 at time 5 agreeing with the colors in , the corresponding evaluation polynomial 6 ,4,5 (ì, ì, ì) is non-zero. For the second iteration, delete vertex 6 from the graph and remove a from leaving us with = { , , }. Now check if there exists a restless path of length 2 ending at any of the neighbors of 6 , i.e., 5 ( 6 ) = { 3 , 5 } at any of the timestamps ∈ {3, 4, 5}. This can be done by verifying if the polynomials 3 ,2, (ì, ì, ì), 5 ,2, (ì, ì, ì) evaluate to a non-zero term for timestamps ∈ {3, 4, 5}. In our case, 5 ,2,3 (ì, ì, ì) evaluates to a non-zero term, which implies that there exists a restless path from 1 to 3 ending at timestamp 3 agreeing with the colors in ′ , so we add the edge ( 5 , 6 , 5) to the solution. We can recursively repeat the second iteration until we reach the vertex 1 to obtain a restless path from 1 to 5 .

A generalization of the approach is described as follows: Let ( , , , , , , ) be an instance of the -RestlessMotif problem. We build an instance ( ℓ , ′ , ℓ , ℓ, ′ , ℓ ) of the -RestlessMotifReach problem for each ℓ ∈ { + 1, , . . . , 2}. For the first iteration, where ℓ = + 1, the graph ℓ is constructed as described in Theorem 5.6 to obtain a new source vertex ′ and a coloring function ′ , ℓ = ∪ ′ ( ′ ), and ℓ = . The graph construction of the -RestlessMotifReach problem for ℓ = + 1 is illustrated in Figure 12 . We apply the algorithm from Theorem 5.6 to obtain ℓ and ℓ .

Let ( ℓ , ℓ ) ∈ ℓ be a (vertex, minimum timestamp) pair such that ℓ ℓ , ℓ = 1. For the first iteration, where ℓ = + 1, we remove the vertex +1 = and remove the incoming and outgoing edges of +1 in +1 to obtain . Let ℓ−1 = ℓ \ ( ℓ ) and ℓ−1 = ℓ . We evaluate the instance ( ℓ−1 , ′ , ℓ−1 , ℓ − 1, ′ , ℓ−1 ) to obtain ℓ−1 . Let ( ℓ−1 , ℓ−1 ) ∈ ℓ−1 be a (vertex, timestamp) pair such that ℓ−1 ℓ −1 , ℓ −1 = 1. As ℓ ℓ , ℓ = 1 there exists an edge ( ℓ−1 , ℓ , ℓ ) ∈ ( ℓ ) in ℓ . In each iteration, we add the edge ( ℓ−1 , ℓ , ℓ ) to the solution and continue the process for each ℓ ∈ { + 1, , . . . , 2}. In total we make queries to the fine-grained oracle. Thus, the runtime of extracting an optimal solution is +1 ℓ=2 2 ℓ ℓ Δ = (2 Δ). Similarly, we have a (2 Δ)-time algorithm for extracting an optimal solution for the -RestlessPath problem.

Using a similar construction, we can improve the runtime of extracting an optimal solution for the PathMotif and -TempPath problems introduced in [71, 72] from ((2 ( + )) ( log + log )) + !) to (2 ( + )).

In this subsection, we prove that under plausible complexity-theoretic assumptions, the algorithms presented for -RestlessMotif and -RestlessMotifReach are optimal.

In particular, the assumption that we rely on is the Set Cover Conjecture [23] (SCC) which is formulated as follows. In the SetCover problem we are given an integer and a family of sets S over the universe = S with = | | and = |S |. The goal is to decide whether there is a subfamily of at most sets 1 , 2 , . . . , ∈ S such that = =1 , i.e., that the selected sets cover the universe . The SCC of Cygan et al. [23] states that there is no algorithm for the SetCover problem that runs in time (2 − ) ( ) (1) for any > 0. In fact, the fastest known algorithm for solving Table 1 . A summary of time and space complexity. Here, is the number of vertices, is the number of edges, is the maximum timestamp, − 1 is the length of path and Δ is the maximum resting time. For each row, the space complexity is ( ).

Time complexity Fine-grained oracle

SetCover runs in time * (2 ) , and an algorithm running in time * ((2 − ) ) for any > 0 has been deemed a major breakthrough after decades of research on the problem. Under SCC, exponential lower bounds for several fundamental problems are known (see e.g., [8, 23, 50] ). However, even if SCC turned out to be false, these results (and Theorem 5.10) are still meaningful: instead of trying to find a faster algorithm for e.g., the arguably richer problem of -RestlessMotif, one can focus on SetCover which is simpler. To obtain our result, it will convenient to recall the ColorfulPath problem in static graphs, and to perform a reduction from that problem to -RestlessMotif problem. Colorful path problem (ColorfulPath). Given a static graph = ( , ) and a coloring function : → [ ], the problem asks if there exists a path of length − 1 in such that the vertex colors of the path are different (i.e., such that each color occurs exactly once). The problem is known to be NP-hard, and known not to admit a * ((2 − ) ) algorithm for any > 0 assuming SCC. Theorem 5.9 (Kowalik and Lauri [49] ). Assuming the Set Cover Conjecture, there exists no * ((2 − ) ) time algorithm for solving the ColorfulPath problem for any > 0. It follows that if we have an algorithm for solving -RestlessMotif with * ((2 − ) ) time for some > 0, we can use it solve ColorfulPath in static graphs using the construction described in Theorem 5.10 within the same time bound. However, from Theorem 5.9 we know that such an algorithm does not exists unless SCC is false. Put differently, assuming SCC, -RestlessMotif does not admit an algorithm running in time * ((2 − ) ) for any > 0. Finally, since -RestlessMotifReach problem generalizes the -RestlessMotif problem, the former problem does not admit an algorithm running in time * ((2 − ) ) for any > 0, assuming SCC.

In this section, we describe our setup and the experimental results to validate our approach and demonstrate its scalability. Our implementation is available as open source [70] .

A high-level intuition of the implementation is as follows: For variables { : ∈ } and { ,ℓ, : ( , , ) ∈ , ℓ ∈ [ ]} we assign a value from the Galois field GF (2 ) . Multiplication between any two field variables is defined as an XOR operation, likewise, multiplying two variables with same value results in a zero-term. We know that the monomials corresponding to walks that are not paths have at least one repeated variable, so the corresponding monomial evaluates to a zero term, while the monomial corresponding to a path evaluates to a non-zero term since there are no repeated variables. It is possible that a monomial corresponding to a path might evaluate to a zero term resulting in a false negative. To reduce the probability of false negatives, we repeat the evaluation with 2 random assignments for variables { : ∈ and ,ℓ, : ( , , ) ∈ , ℓ ∈ [ ] . In theory, the false negative probability of our algorithm is 2 − (2 − 1). For our experiments, we choose the field size = 64, which makes the false negative probability negligible.

Modern CPUs have very high arithmetic and memory bandwidth, however, the bandwidth comes at the cost of latency. Each arithmetic and memory-access operation is associated with a corresponding latency factor, and often the memory-access latency 27 is orders of magnitude greater than the arithmetic latency. As such, the challenge for efficient implementation engineering is to keep the arithmetic pipeline busy while fetching data from memory for the subsequent arithmetic operations. Memory bandwidth can be improved by using coalesced-memory access, that is, by organizing the memory layout such that the data for consecutive computations are available in consecutive memory addresses. In addition, we can use hardware prefetching to fetch the data required in subsequent computation while performing computation on the data, which is currently in the memory. Arithmetic bandwidth can be improved using vector extensions, that is, by grouping the data on, which the same arithmetic operations are executed. More precisely, if we are executing the same arithmetic instructions on different operands or data, we can group the operands using vector extensions to execute arithmetic operations in parallel. For more technical details related to implementation engineering we refer the reader to [12, 45, 72] .

Our implementation is written in the C programming language with OpenMP constructs to achieve thread-level parallelism. Vector parallelism is achieved by enabling parallel executions of the same arithmetic operations, which make use of advanced vector extensions (AVX2). Additionally, we use carry-less multiplication of one quadword (pclmulqdq) instruction set to enable fast finite-field arithmetic. The finite-field arithmetic implementation we use is from [12] .

Our engineering effort boils down to implementing the recursions in Equations (2) and (4) and evaluating the polynomial using 2 ℓ random substitutions for the -variables. Recall that from the construction of the generating function the -variables are unique, so we generate the values of -variables using a pseudorandom number generator. The values of the -variables are computed using Equation (4). Our implementation loops over four variables: the outer most loop is over [ℓ], the second loop is over [ ], the third loop is over , and the final loop is over {0, . . . , ( )} for ∈ . In Equation (4), computing the polynomial ,ℓ, ( ì, ì) is independent for each ∈ if we fix ℓ and , so the algorithm can be thread-parallelized up to | | = threads. We make use of the OpenMP API using the omp parallel for construct with default scheduling over vertices in to achieve thread parallelism. Additionally, performing 2 ℓ random substitutions of -variables is independent of each other, so each of the 2 ℓ evaluations can be vector-parallelized. We achieve this by grouping the arithmetic operations on 2 ℓ random substitutions of variables in and enabling the vector extensions from AVX2. Recall that our inner-most loop is over {0, . . . , ( )}, so we arrange the memory layout as × to saturate the memory bandwidth. We also employ hardware prefetching by forcing the processor to fetch data for subsequent computations while we are still performing the computation on the data, which is already in the memory.

Our implementation uses ( + ) memory, which is due to the adjacency list representation of the temporal graphs.

Preprocessing. In the restless reachability problems considered in our work, we compute reachability from a given source vertex to all other vertices without an explicit restriction on the time window. As such, we do not see a straightforward approach to preprocessing the temporal graph to reduce its size using heuristic preprocessing techniques such as slicing within a time window, i.e., considering the edges between a minimum and maximum timestamp window. Alternatively, we can merge to obtain a static graph, compute reachability on the static graph, and reconstruct a temporal graph by only using the vertices, which are reachable in the static graph. Such a preprocessing technique is correct since there exists a restless path between any two vertices in a temporal graph only if there exists a path in the corresponding static graph, while the other direction is not always true. However, most of the datasets considered in our experiments have a connected static underlying graph, and therefore we do not see a significant reduction in graph size.

For the restless reachability problems with additional color constraints i.e., for the -RestlessMotif and -RestlessMotifReach problems, we can take advantage of two preprocessing techniques to reduce the graph size: ( ) by removing all the vertices whose vertex colors do not match with the multiset colors; ( ) by merging the temporal graph to a static graph instance, build a vertex-localized sieve on the static graph, and reconstruct the graph using the set of vertices reachable in the static graph instance. Note that these are heuristic approaches to reduce the graph size and we do not claim any theoretical bounds for the reduction in the graph size. For a detailed discussion of preprocessing using vertex-localized sieving we refer the reader to an earlier work [72, § Preprocessing].

Here we describe the hardware details and the input graphs used for our experiments.

Hardware. We make use of two hardware configurations for our experiments. The experiments make use of all the cores. Additionally, we make use of AVX2 and hardware prefetching to saturate the arithmetic and memory bandwidth, respectively. Input graphs. We use both synthetic and real-world graphs in our experiments. For synthetic graphs, we use the temporal-graph generator from Thejaswi et al. [72, § 9.3] , in particular we make use of -regular and power-law graphs. The regular graphs are generated using the configuration model [13, § 2.4 ]. The configuration model for powerlaw graphs is as follows: given non-negative integers , , , and < 0, we generate an -vertex graph such the following properties roughly hold: ( ) the sum of vertex degrees is ; ( ) the distribution of degrees is supported at distinct values with geometric spacing; and ( ) the frequency of vertices with degree is proportional to . The edge timestamps are assigned uniformly at random in the range [ ]. Both directed and undirected graphs are generated using the same configuration model, however, for directed graphs the orientation is preserved. We ensure that the graph generator produces identical graph instances in all the hardware configurations.

For real-world graphs, we use the co-presence dataset from socio-patterns [31] , Koblenz network collections [53] , Copenhagen study network [65] , and public-transport networks [52] . For a description of the datasets, see the respective references. The preprocessing details of each dataset is described below. We preprocess the datasets to generate a graph by renaming the location identifiers (or vertices) in the range from 1 to the maximum number of locations (or vertices) available in the dataset. If the time values in dataset are Unix timestamps, we approximate the value to the closest second rounded down before assigning an unique timestamp identifier. For datasets from socio-patterns, we reduce the maximum timestamp by dividing each timestamp by 20 and rename the timestamps in the range from 1 to the difference between the maximum and minimum timestamps. Since socio-patterns datasets are undirected contact-networks we replace each undirected edge with two directed edges in both directions. For the Koblenz datasets we round the timestamp to the closest day. Dataset statistics. For each real-world dataset we report the number of vertices , the maximum timestamp , the number of temporal edges , and the average temporal degree avg = . Furthermore, for each dataset we construct a static undirected graph or an underlying graph by considering the edges without the timestamp information ignoring multiple edges (if any) between the same set of vertices. For a temporal graph , we denote the corresponding underlying (static) graph as ↓ . For the underlying graph we report the number of edges ↓ , the average degree ↓ avg , the length of the diameter ↓ max , the feedback edge number (FEN), and the feedback vertex number (FVN). The dataset statistics are reported in Table 2 .

The average degree ↓ avg = ↓ is the ratio of number of edges and the number of vertices in the static graph. The diameter of a static graph is the length of a longest shortest path between any two vertices and it can be computed in time ( ↓ ), where is number of vertices and ↓ is number of edges, however, the runtime can be further reduced to ( ↓ ) in practice [22] . The diameter of the underlying graph is neither a lower bound nor an upper bound on the maximum length of the restless path. We report this value only to show that usually the path length parameter is orders of magnitude less than the parameters FVN and FEN in most real-world graph datasets.

The feedback edge number of a static graph = ( , ) is the minimum number of edges that need to be removed from in order to make acyclic. Formally, a set ⊆ is a feedback edge set if ( , \ ) does not contain a cycle. In other words, the feedback edge number of is the size of a minimum feedback edge set for . The feedback edge number can be computed in polynomial-time by computing a maximum spanning forest of and by taking its edge-complement.

The feedback vertex number of a static graph = ( , ) is the minimum number of vertices that need to be removed from in order to make acyclic. Formally, a set ⊆ is a feedback vertex set if ( \ , \ {( , ) : ∈ or ∈ }) does not contain a cycle. The feedback vertex number of is the size of minimum feedback vertex set of . In contrast to the feedback edge number, computing the feedback vertex number is NP-hard (see e.g., [44] ). For computing the feedback vertex number, we use the solvers from the work of Iwata et al. [39, 40] .

In this subsection we discuss baseline approaches considered for comparison. Additionally, we present careful justification on why certain approaches used to solve temporal reachability problems fail to solve restless reachability problems.

Random (restless) walks. Algorithmic approaches based on random walks can be used to estimate reachability in temporal graphs. The approach works by performing a random walk in a temporal graph and update reachability using the transitive closure A restless walk A temporal path (highlighted in blue) Fig. 13 . An illustration of infeasibility to transform a restless walk to a restless path. On the left, a restless (temporal) walk 1 1 , 2 ,1 2 2 , 3 ,2 3 3 , 4 ,3 4 4 , 2 ,4 2 2 , 5 ,5 5 from vertex 1 to 5 , where resting time of vertices is ( 1 ) = · · · = ( 5 ) = 2. On the right, a temporal path 1 1 , 2 ,1 2 2 , 5 ,5 5 from 1 to 5 (highlighted in blue) obtained by removing the loop (highlighted in red). Observe that the obtained temporal path is not a restless path since the difference in edge timestamps entering and leaving 2 is 4 > ( 2 ) = 2. In conclusion, even though there is a restless walk from 1 to 5 , there exists no restless path from 1 to 5 .

property by respecting time constraints. More precisely, let , and be distinct vertices. Now, if there exists a temporal walk from to ending at time and a temporal walk starting at time from to such that ≤ , then there is a temporal walk from to . Most reachability methods using temporal walks can be extended to estimate reachability with temporal paths, since a temporal walk can be transformed into a temporal path by removing loops in the walk. However, a similar approach of transforming reachability using restless walks to restless paths is not straightforward, since a restless walk cannot be transformed into a restless path by simply removing loops, as it may not satisfy waiting-time constraints (see Figure 13 ).

Temporal graph expansion. A time-expansion of a temporal graph to a static directed graph has been applied to reduce temporal reachability to reachability questions in static directed graphs [17, 55, 68, 81, 88] . Again, the approach can be used to solve reachability problems when vertices need to be connected via a restless walk, however, it fails to solve reachability problems when vertices must be connected via a restless path. Here, we describe a transformation of a temporal graph to a static directed graph which respects waiting-time restrictions called -expansion, and describe the limitations of this approach. Let = ( , ) be a temporal graph with maximum timestamp and let : → N + be a vertex-dependent waiting time. The -expansion of is a static directed

For an illustration, see Figure 14 . Observe that | ′ | = | | and | ′ | = (Δ + 1) | |, where Δ = max ∈ ( ). Finally, note that ↑ ( ) can be computed efficiently.

From the construction, it is easy to see that there exists a restless walk from vertex to in if and only if there exist a directed path from vertex ℓ to ℓ ′ in ↑ ( ) for some ℓ, ℓ ′ ∈ [ ] such that ℓ ≤ ℓ ′ . Using -expansion, we can use existing algorithmic approaches for solving reachability problems in static directed graphs to solve reachability problems where vertices must be connected via a restless walk. Observe that even though there exists a directed path from 1 1 to 5 5 in ↑ ( ), there is no restless path from 1 to 5 in , so it is not straightforward to employ this approach to solve reachability problems when vertices must be connected via a restless path. Index construction. In a 2-hop labeling of static graphs, each vertex ∈ is assigned a label-set pair ( in ( ), out ( )) such that is reachable from each ∈ in ( ) ⊆ and each ∈ out ( ) ⊆ is reachable from . From the transitive closure property, it follows that a vertex is reachable from a vertex if and only if out ( ) ∩ in ( ) ≠ ∅. The approach is extended to solve temporal reachability using a transformation to a directed acyclic graph (DAG) [82, Section 3] . Here, the authors try to answer reachability questions in temporal graphs constrained by time intervals. More specifically, given two vertices , ∈ and timestamps 1 , 2 ∈ [ ], the goal is to decide whether is reachable from via a temporal path (or a temporal walk) such that the timestamps of the edges in the path are in range { 1 , 1 + 1, . . . , 1 + 2 }. A key difference in our reachability model is that the transition time of an edge can be zero which makes the -expansion described in Figure 14 a static directed graph but not a DAG. Additionally, we established that even though two vertices are reachable via a directed path in the -expansion, it does not imply that there exists a restless path connecting the vertices in the temporal graph.

We would like to note that the RestlessPath problem is NP-complete for all integers Δ ≥ 1 and ≥ Δ + 2, even if there exists at most one temporal edge between any two vertices [17, Theorem 5] . So it is highly unlikely that there exists a straightforward extension of 2-hop cover to solve the RestlessPath problem even if we constrain time intervals.

Parameterized (exact) algorithms. Casteigts et al. [17] presented algorithms for solving the RestlessPath problem parameterized by the feedback edge number of the underlying graph and the timed feedback vertex number (TFVN) of the temporal graph. Additionally, they showed that the TFVN of the temporal graph is lower bounded by the FVN of the underlying graph. For a temporal graph = ( , ) with maximum timestamp , the timed feedback vertex set of is a set ⊆ × [ ] of vertex appearances such that ( − ) ↓ is acyclic, where − = ( , ′ ) such that ′ = \ {( , , ) ∈ : ( , ) ∈ or ( , ) ∈ } and ( − ) ↓ is the underlying graph of ( − ). The timed feedback vertex number of a temporal graph is the minimum cardinality of a timed feedback vertex set of . From the statistics in Table 2 , it is clear that the values of FVN and FEN are orders of magnitude greater than the diameter of the graph, for most datasets. Most importantly, it appears difficult to change the value of the parameters FEN and FVN, whereas the length of the restless path to be found can be readily varied. Indeed, as we will see, such an approach leads to a solution scaling to graphs with millions of temporal edges provided that the parameter remains small enough.

Exhaustive search (baseline). Finally, we consider an exhaustive search algorithm based on temporal depth-first-search (dfs), which a parameterized algorithm with respect to the maximum degree of the graph max . We perform temporal dfs starting from a source by respecting waiting-time constraints and restrict the depth of the search to . We report the minimum reachability time for the vertices that are reachable from by at most − 1 hops. The time complexity of the exhaustive search algorithm is ( max ). As demonstrated in previous work [71, 72] , and also shown in our experiments (see Subsection 6.4), the exhaustive search does not scale for large scale-free graphs. In particular, many real-world graphs exhibit a power-law degree distribution, or more generally, scale-free structure. However, the exhaustive search algorithm is highly practical for some structured graphs such as graphs that are close to being -regular with small maximum degree. In our experiments, we refer the exhaustive search algorithm as the baseline.

Discussion. We stress that our focus is on exact computation of restless reachability. As such, we do not compare our proposed algorithms to probabilistic methods, heuristics or approximation schemes. Further, to the best of our knowledge, there is no publicly available implementation for solving the restless reachability problem that scales to large graphs such as those considered in our experiments. For instance, we argue that the algorithms presented by Casteigts et al. [17] are unlikely to perform adequately in practice given their exponential dependency on a structural parameter that, in many real-world networks, has a high value (see Table 2 ). In addition, it is not immediate how index computation techniques such as 2-hop or 3-hop covers or location based indexing would extend to solve restless reachability.

Finally, a careful reader might question our focus on exact computation by recalling that our algorithm has a false negative probability of (2 − 1)/2 . However, by fixing a suitable value for and potentially running our method multiple times, we can make this probability arbitrarily close to zero. For concreteness, we choose = 64 for our experiments, which means that when say = 10, the per-vertex false negative probability is less than 2 59 ≈ 5.76 · 10 −17 . In comparison, a modern consumer CPU running for at least five days has a 1 in 330 chance of a hardware failure due a machinecheck exception, a 1 in 470 chance of a disk subsystem failure, and 1 in 2700 (≈ 3.7·10 −4 ) chance of a DRAM memory failure [57, Figure 2 ], all significantly more likely than our algorithm making an error. Table 5 ---10 10 → {10} - Table 6 ---10 5, 10 → {Δ} - Figure 17 -

Case study (Socio-patterns) 

In this section we report our experimental results. The experiments are designed to study the following aspects: ( ) scalability of the algorithm to graphs with up to 10 million edges on the workstation configuration; ( ) scalability of the algorithm to large graphs with up to one billion edges on the computenode configuration; ( ) computing restless reachability in real-world datasets; and ( ) a case study investigating the effectiveness of different vertex-selection strategies to act as barriers and minimize the spread of diffusion processes (e.g., infectious diseases) through the temporal network. An overview of our experiments is available in Table 3 . In our experimental results, runtime refers to the empirical running time and memory refers to the peak-memory usage of our implementation. Scalability. To demonstrate the scalability of the algorithm we experiment with synthetic graphs. In Figure 15 We observe an exponential increase in the runtime with the increase in length of the restless path, as predicted by the theoretical analysis. The source vertex is chosen uniformly at random. The variance in runtime between the independent graph inputs is very small for the algebraic algorithm as compared to the baseline, which exhibit high variance in runtime. We observe that our baseline fails to report the solution for power-law graphs with = 10 3 , = 10 6 , and = 10. Note that we terminate experiments that take more than ten hours. The runtime of the exhaustive search algorithm depends on the degree distribution of the graph: if the temporal dfs visits a high-degree vertex then the baseline algorithm takes long time to complete the execution. However, the baseline is efficient for sparse -regular graphs, where the maximum degree is small. Again, for scaling with respect to the length of the restless path our baseline failed to report a solution for ≥ 10. We terminate the experiments, which take more than ten hours of runtime. Our implementation can handle the -RestlessReach problem on a graph instance with one million nodes, ten million edges, and path length = 10, in less than 20 minutes using less than 2 gigabytes of working memory on the workstation configuration.

In Figure 15 (center-right), we report the runtime of the algorithm as a function of the maximum resting time Δ. The experiments are performed on five independent random power-law graphs for each configuration of Δ = 10, 20, . . . , 100, : → {Δ} with fixed values of = 10 5 , = 100, = 100, = −1.0, = 100, and = 10. We do not observe a linear-scaling of the runtime as the theoretical analysis tells us. A possible explanation is that the graphs used for the experiments are sparse, and there is not enough workload to saturate the empirical arithmetic and memory bandwidth of the hardware, simultaneously. However, with the increase in the resting time Δ we need to perform more arithmetic operations there by improving the arithmetic and memory bandwidth. This is due to the fact that, the implementation enables more streamlining of the memory and arithmetic pipeline of the computer hardware when there is enough workload to parallelize.

Our final scalability experiments report the effect of the graph density on scalability. In Figure 15 (right), we report the runtime of the algorithm as a function of the graph density. Density of the graph is the ratio of number of edges and the number of vertices. The experiments are executed on five independent random power-law graphs for each configuration of = 10, 10 2 , 10 3 , 10 4 and corresponding values of = 10 5 , 10 4 , 10 3 , 10 2 , with fixed values of = 10 6 , = 100, Δ = 10, : → {Δ}, and = 10. We observe that our implementation performs better for dense graphs. Again a possible explanation is that for sparse graphs there is not enough work to keep both the arithmetic and memory pipeline busy, simultaneously. This also presents us a challenge to design an efficient implementation for handling sparse graphs.

All experiments are executed on the workstation configuration using all cores with directed graphs. Note that we demonstrated the scalability of the algorithm for -RestlessReach problem instances, however for other problem instances the runtimes are similar.

Extracting an optimal solution. Our second set of experiments compares the runtime of the algorithm for extracting an optimal restless path between a source and a destination using the decision oracle and the fine-grained oracle. Recall that the algorithm only returns a yes/no answer for the existence of a solution and we need multiple queries to the oracle to obtain a solution. Using a decision oracle we require ( log log ) queries in expectation to obtain an optimum solution as compared to queries using a fine-grained oracle (see Section 5.9). In Figure 16 we compare the runtime (left) and the peak-memory usage (center) of the decision oracle and the fine-grained oracle for extracting an optimum solution for five independent random power-law graphs for each configuration of = 10 3 , . . . , 10 7 with fixed values of = 100, = 100, Δ = 10, : → {Δ} and = 10. The source and the destination are chosen at random. We observe little variance in runtime for the fine-grained extraction as compared to oracle extraction. For large graphs with hundred million edges the fine-grained extraction is up to four times faster than the oracle extraction. Even though in theory we reduce the number of queries by a factor of log log , in practice we do not obtain a significant improvement in the empirical runtime. When extracting a solution using the decision oracle, recall that for each query of the oracle we recursively divide the graph into smaller subgraphs. For each smaller subgraph, we build the multilinear sieve and thereby reduce the empirical runtime of each query. In addition, while the the expected number of queries is bounded by ( log log ) in worst case, this bound is not always met in practice. For a given instance, the number of queries required to extract a -vertex subgraph varies depending on the source and the destination, resulting in high variance in the extraction time for extraction via self-reducibility. However, there is considerably less variance in the runtime of the fine-grained extraction approach.

The experiments are executed on the computenode configuration using all cores. We report the runtime of extraction for the -RestlessMotif instances, but the runtimes are similar for the -RestlessPath instances.

Graph topology. Here we study the effect of graph topology on runtime of the algorithm. In Figure 16 (right), we report the runtime of the algorithm for five independent -regular random graph instances for each configuration of = 10 2 , . . . , Experiments with real-world graphs. Our next set of experiments reports the runtime of the algorithm for finding restless reachability and extracting a restless path in real-world datasets. The description of the datasets used for our experiments is available in Section 6.2.

In Table 4 and 5 we report the runtime for finding restless reachability in real-worlds graphs with = 5 and = 10, respectively. For each dataset we report the maximum runtime of five independent runs by choosing the source vertex ∈ uniformly at random for each ∈ {5, 10}, for fixed value of the maximum resting time Δ = 10, and : → {Δ}, i.e., the resting time is constant for all the vertices except the source , which has the maximum resting time ( ) = . In Column 2 we report the runtime for solving the -RestlessReach problem, while Column 3 reports the runtime for solving the RestlessReach problem by restricting the path length to − 1. Note that here we solve the atm--RestlessReach problem where we find the set of vertices that are reachable from a given source via a restless path with length at most − 1. Column 4 is the ratio of Column 3 and Column 2. Next, in Columns 5 and 6 we report the runtime of extracting a solution using a decision oracle and a fine-grained oracle, respectively. Column 7 is the ratio of Column 6 and Column 5. Finally, in Column 8, we report the peak memory usage of the fine-grained extraction. All runtimes are in seconds. The experiments are executed on computenode configuration using all cores.

We can solve restless reachability in each real-world graph dataset in Table 2 in less than one minute by restricting the length of the restless path to 5, and in less than two hours using at most 14 Gb of memory for = 10. For instance, we can solve restless reachability by limiting to 10 in a real-world graph dataset with more than 37 million directed edges and more than 19 thousand timestamps in less than one hour on a Haswell desktop using less than 6 Gb of memory. The reported runtimes are in seconds.

From the results (see Column 3), we see that solving atm--RestlessReach takes less than twice the empirical running time than that of -RestlessReach, in most of the input graph instance. Extracting a solution using fine-grained extraction is effective for large graphs, given that is not too large. For instance, we obtain an 8-time speedup in computation using fine-grained extraction as compared to oracle extraction in a graph with more than hundred thousand vertices and more than eight hundred thousand edges with = 10. Reachability. Our next set of experiments studies the restless reachability in sociopatterns dataset. In particular we solve the atm--RestlessReach problem where we find the set of vertices reachable from a given source via a restless path of length at most − 1. Reachability is the ratio of the number of vertices that are reachable with a restless path to the total number of vertices. In Figure 17 we report the variance and mean of reachability as a time-series for five independent graph instances for each dataset with Δ = 5 (top-row) and Δ = 20 (bottom-row). More precisely, for a given dataset we generate five graph instances by choosing a source vertex uniformly at random and assign the resting times uniformly at random in the range [Δ]. We limit the length of the restless path to 9, i.e., = 10 and solve the atm--RestlessReach problem.

We observe high variance in reachability among the independent source vertices for LH10, InVS15, LyonSchool, and Thiers13 datasets, and smaller variance for InVS13 and SFHH. We also see that in all datasets, except LH10, reachability approaches its maximum value 1, within the total number of timestamps available in each dataset, however, this happens at different times for each dataset, and with a different pace.

In Table 6 , we report the runtime for solving the atm--RestlessReach problem in socio-patterns datasets. The reported runtime is the maximum of five independent runs by choosing the source vertex ∈ uniformly at random with = 10 (fixed) and Δ = 5, 10, : → {Δ} (fixed). The resting time is constant for all the vertices except the source , which has the maximum resting time ( ) = . For instance, we can solve -RestlessReach problem by limiting = 10 in a real-world graph dataset with more than 37 million directed edges and more than 19 thousand timestamps in less than one hour on workstation configuration using less than 6 Gb of memory. The reported runtimes are in seconds.

Our final set of experiments studies the change in restless reachability in the presence of a set of barrier vertices ′ ⊆ called separators, which must not be included in the restless path. In an epidemic model, the separators can be viewed as a subset of the population, all immune and/or vaccinated. It is known that finding a set of temporal separators with minimum size, which destroy all the restless paths between any two vertices, is 2 -hard [17] . A promising heuristic to finding a minimum set of separators is choosing the vertices with high temporal-betweenness centrality. Unfortunately, computing the betweenness centrality in temporal graphs is intractable [16] .

The experiments performed in this case study are to evaluate the effectiveness of our algorithm to answer queries for finding an effective immunization strategy in an epidemic model where the disease propagation is via a restless path. To demonstrate this we use two heuristics for finding separators: ( ) choose vertices at random and ( ) choose vertices with maximum temporal degree. Note that these immunization strategies are simple and without theoretical guarantees. Towards this end, we would like to investigate effective approximation or heuristic schemes to find temporal separators, which reduce the fraction of vertices reachable from a given source vertex via a restless path in future work.

Given an instance ( = ( , ), , ) of the -RestlessReach problem and a set ′ ⊆ of separators, we introduce a coloring function : \ { ′ ∪ } → {1}, ( ) = 2 and : ′ → {3} and = {1 ℓ−1 , 2} for ℓ ∈ [ ]. We query the FineGrainedOracle with instance ( ′ = ( , \ { , , } ∈ ), , ℓ, ) for each ℓ ∈ {2, . . . , }. By assigning color 3 ∉ to the separators in ′ , we make sure that none of the separators are part of the restless path agreeing the multiset of colors in . Note that here we solve the atm--RestlessReach problem, in other words we find the set of vertices which are reachable from the source via a restless path of length at most − 1.

In Figure 18 , we report the variance of reachability in real-world graphs by choosing 5% of the vertices uniformly a random (top-row) and 5% of the vertices with maximum degree (second-row) as separators. Figure 19 reports the same experiments with 5% replaced with 25%. For each dataset we generate five graph instances, choose source vertices at random and assign resting times uniformly at random in the range [Δ] for Δ = 10. Note that we use the same instances in the reachability experiments described above. Reachability is the ratio of number of reachable vertices to the total number of vertices excluding separators. From the experimental results we observe high variance in the reachability among independent source vertices and the rate of increase of the reachability with time varies depending on the source vertex. More importantly, even though we expect (empirically) that by choosing vertices with high degree as separators should decrease the reachability as compared to choosing the vertices at random, this is not true for all the datasets. We only observe this phenomenon in SFHH and Thiers13 datasets for choosing 5% of the vertices as separators and in InVS15 and LyonSchool datasets while choosing 25% of the vertices as separators.

In Figure 20 , we report the variance of reachability in real-world graphs by choosing 5%, 10%, and 25% of the vertices uniformly a random (top-row) and 5%, 10%, and 25% of the vertices with maximum degree (second-row) as separators. Again, for each dataset we generate five graph instances, choose source vertices at random and assign resting time uniformly at random in the range [Δ] for Δ = 10. Note that we use the same instances in the reachability experiments described above. We observe that reachability reduces with an increase in the number of separators, as expected. Again, even though it is expected (empirically) that choosing vertices with maximum degree to reduce the reachability significantly compared to choosing separators at random, surprisingly enough, this is not true for all datasets. For instance in LyonSchool dataset choosing 10% of the separators at random reduces the average reachability more than choosing vertices with maximum degree as separators. So the heuristic approach of choosing vertices with maximum degrees might not be effective across datasets. This presents us a interesting question of finding a small a set of separators in temporal graphs under resting time restrictions. Also note that the input graph datasets are small world graphs, meaning that the diameter of the underlying graph is small, so the vertices are highly connected (see Table 2 ).

In this work, we studied a family of reachability problems in temporal and vertexcolored temporal graphs under waiting-time restrictions. We presented an algebraic algorithm framework for solving restless reachability problem we proposed, running in (2 Δ) time and ( ) space. We presented evidence that the algorithms for solving variants of the restless reachability problems involving colors presented in this work are optimal under plausible complexity-theoretic assumptions. Further, we engineered an open-source implementation of our algorithm, and demonstrated its viability in experiments on graphs with millions of temporal edges from real-world datasets. Finally, we applied the algorithm we developed in a case study for estimating the change in disease spreading with the presence of people with immunity. Our finding is that heuristic approaches such as selecting vertices with high degree as separators are not effective in all the graph datasets. Towards this end, we would like to investigate effective ways to choose a small set of separators under waiting time restrictions to contain the spread of the disease in the network.

We believe our algorithms, based on multilinear and constrained multilinear sieving, can be extended even further to solve a range of other pattern-detection problems in temporal graphs, including finding arborescences, connected temporal subgraphs and temporal subgraphs with additional color constraints on the vertices. We also note that our temporal reachability setting corresponds to the SIS (susceptible-infectioussusceptible) epidemic model. Another interesting direction is to develop algorithms for temporal reachability that corresponds to the SIR (susceptible-infectious-removed) model. Table 6 . Computing restless reachability in socio-patterns dataset using the workstation configuration. We report runtime for solving atm--RestlessReach problem with = 10 (fixed). Table 7 . List of symbols. 

Efficient management of transitive relationships in large data and knowledge bases

Biomolecular network motif counting and discovery by color coding

Tracking disease progression by searching paths in a temporal network of biological processes

Efficient limited-time reachability estimation in temporal networks

The role of social networks in information diffusion

DNA rendering of polyhedral meshes at the nanoscale

Narrow sieves for parameterized paths and packings

Probably optimal graph motifs

Determinant Sums for Undirected Hamiltonicity

Fast Witness Extraction Using a Decision Oracle

Constrained Multilinear Detection and Generalized Graph Motifs

Engineering Motif Search for Large Graphs

Random Graphs (second ed.). Cambridge UP

Distance oracles in edge-labeled graphs

Complex brain networks: graph theoretical analysis of structural and functional systems

Algorithmic Aspects of Temporal Betweenness

Finding Temporal Paths Under Waiting Time Constraints

An efficient algorithm for answering graph reachability queries

Outbreak minimization vs influence maximization: an optimization framework

Reachability and distance queries via 2-hop labels

The shortest route through a network with time-dependent internodal transit times

On computing the diameter of real-world undirected graphs

On problems as hard as CNF-SAT

Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. 2015. Parameterized algorithms

Temporal dynamics of spontaneous MEG activity in brain networks

Algorithms for minimum-cost paths in time-dependent networks with waiting policies

Modelling disease outbreaks in realistic urban social networks

Quantifying SARS-CoV-2 transmission suggests epidemic control with digital contact tracing

Constrained shortest path problems: state-of-the-art and recent advances

Temporal graph classes: A view through temporal separators

Can co-location be used as a proxy for face-to-face contacts?

Spatio-temporal network databases and routing algorithms: A summary of results

Reorganization of functionally connected brain subnetworks in high-functioning autism

Finding Top-k Shortest Path Distance Changes in an Evolutionary Network

Efficient computation of optimal temporal walks under waiting-time constraints

Network reachability of real-world contact sequences

Temporal networks

Shortest path problems with resource constraints

Half-integrality, LP-branching, and FPT algorithms

Diffusion on social networks

Computing Label-Constraint Reachability in Graph Databases

3-hop: a high-compression indexing scheme for reachability query

Reducibility among combinatorial problems

Engineering Motif Search for Large Motifs

Maximizing the spread of influence through a social network

Faster Algebraic Algorithms for Path and Packing Problems

Limits and Applications of Group Algebras for Parameterized Problems

On finding rainbow and colorful paths

The Set Cover Conjecture and Subgraph Isomorphism with a Tree Pattern

From the brain to public transport: Applications of network science

A collection of public transport network data sets for 25 cities

KONECT: the Koblenz network collection

Novel polynomial basis with fast Fourier transform and its application to Reed-Solomon erasure codes

Temporal network optimization subject to connectivity constraints

An introduction to temporal graphs: An algorithmic perspective

Cycles, Cells and Platters: An Empirical Analysis of Hardware Failures on a Million Consumer PCs

Epidemic processes in complex networks

Answering reachability and K-reach queries on large graphs with label constraints

Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond

Focused clustering and outlier detection in large attributed graphs

Hanghang Tong, and Christos Faloutsos. 2013. Fractional immunization in networks

Michalis Faloutsos, and Christos Faloutsos. 2010. Virus propagation on time-varying networks: Theory and immunization algorithms

Reconstructing an epidemic over time

Interaction data from the copenhagen networks study

Fast Probabilistic Algorithms for Verification of Polynomial Identities

A network of protein-protein interactions in yeast

Arrow: Approximating reachability using random walks over web-scale graphs

An improved algorithm for transitive closure on acyclic digraphs

Restless-reachability-experimental-v1.0: release

Pattern detection in large temporal graphs using algebraic fingerprints

Finding Path Motifs in Large Temporal Graphs Using Algebraic Fingerprints

From static to temporal network theory: Applications to functional brain connectivity

Approximate distance oracles

Fast best-effort pattern matching in large attributed graphs

On the vulnerability of large graphs

Public transport networks: empirical analysis and modeling

Constrained Route Planning over Large Multi-Modal Time-Dependent Networks

Finding paths of length in * (2 ) time

Path Problems in Temporal Graphs

Efficient Algorithms for Temporal Path Computation

Reachability and time-based path queries in temporal graphs

Computing shortest, fastest, and foremost journeys in dynamic networks

Graph reachability queries: A survey. In Managing and Mining Graph Data

Constrained shortest path query in a large time-dependent graph

Dynamics of information diffusion and its applications on complex networks

Probabilistic algorithms for sparse polynomials

Hendrik Molter, and Rolf Niedermeier. 2020. The complexity of finding small separators in temporal graphs

We acknowledge the support of Aalto Science-IT with computational resources. This research is supported by the Academy of Finland projects AIDA (317085) and MLDB (325117), the ERC Advanced Grant REBOUND (834862), the EC H2020 RIA project So-BigData (871042), and the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.

The authors declare that they have no conflict of interest.