Temporal graph exploration: restrictions and relaxations

This thesis considers the problem of exploring temporal graphs. A temporal graph G = hG1; :::;GLi of order n is a sequence of L undirected graphs (or layers) indexed by the timesteps t 2 f1; : : : ;Lg, such that V (G1) = V (G) and  E(Gt)  E(G) for some underlying graph G with order n. To explore G is to visit each vertex at least once via a sequence of edge-traversals (called an exploration schedule), with each consecutive edge traversed during a timestep strictly greater than the last. The arrival time of an the timestep during which the last unvisited vertex is reached for the first time.There exists an algorithm producing exploration schedules with arrival time O(n2) for any always-connected (i.e., Gt is connected for all t 2 f1; : : : ;Lg) temporal graph, and an infinite family F of always-connected temporal graphs for which any exploration schedule has arrival time (n2) [38, 86]. We isolate a number of characteristics held by the members of F and prove lower/upper bounds on the arrival time of exploration schedules for temporal graphs that are restricted from possessing them. First, we consider structural restrictions in which an input temporal graph has (1) degree upper bounded by in each layer; and (2) at most k edges `missing' from the underlying graph in each layer; subquadratic upper bounds are proved in each case. We then consider `relaxed' exploration schedules that can traverse a ?nite number of edges ( 1) in each timestep, focusing on the cases when 2 or n=k traversals are allowed. We also consider, from a complexity standpoint, a number of relaxed problem variants, in which (1) less than n vertices are required to be explored by a candidate, and (2) an unlimited but ?nite number of edge traversals can be made by a candidate exploration schedule, providing both FPT-membership results and hardness/NP-completeness results.