Algorithmic Aspects of Temporal Graphs

The design and analysis of algorithms on graphs is a major sub-discipline of Computer Science. Graphs (composed of vertices and edges) are ubiquitous not only in Computer Science and Mathematics but across the whole spectrum of Science and Engineering. They are used to abstractly model diverse real world systems, where vertices and edges represent elementary system units and some kind of interactions between them, respectively. However, in modern systems this modeling paradigm using static graphs may be restrictive or oversimplifying, as the interactions usually change over time in a highly dynamic manner. For example, friendships are added and removed over time in a social network and links in a communication network may change dynamically, either according to a specific known pattern (satellites following a trajectory) or in an unpredictable manner (mobile ad hoc networks). The common characteristic in all these application areas is that the system structure, i.e. graph topology, is subject to discrete changes over time.

A temporal graph consists of an underlying graph and a time-labeling function that assigns to every edge of the graph a set of discrete time-labels. These time-labels are drawn from the set of natural numbers, indicating the discrete time points where the corresponding edge is present. The conceptual shift from static to temporal graphs has a significant impact on the definition of the basic graph parameters and metrics, and thus also on the type of tasks that can be performed. Graph properties can be generally classified into a-temporal (i.e. satisfied at every time point) and temporal ones (i.e. satisfied over time). For example, although global connectivity may not hold at any single time point, communication routes may still exist over time between each pair of nodes. In particular, a path in the underlying (static) graph G is called temporal if there exists an increasing sequence of time-labels as one walks along the edges of the path.

Classic metrics from static graph theory can usually be generalized in various ways to natural metrics in temporal graphs. For example, depending on the application domain, the temporal analogue of a ``shortest path'' between two vertices u,v can be translated as (a) the topologically shortest path, having the smallest number of edges, (b) the fastest path, having the smallest time duration, or (c) the foremost path, arriving as early as possible (regardless of the starting time). The computational complexity of a static graph problem may or may not carry over to its temporal counterpart; this strongly depends on the problem and the metric concerned. It is known that a shortest / fastest / foremost temporal path can be computed in polynomial time; however, computing strongly connected components is NP-complete in temporal graphs, in contrast to the static case. Although some temporal graph optimization problems may be hard to solve or to approximate in the worst case, an optimal solution may be efficiently computable when we restrict in the input temporal graph (a) its underlying topology, or (b) the time-labeling, i.e. the temporal pattern in which the time-labels appear, or both. Restricting the input temporal pattern is a distinguishing temporal aspect with no immediate analogue in static graphs.

Within the proposed research we plan to investigate the various temporal graph problems, as well as to more deeply understand their underlying combinatorial structure. In addition to temporal path-related problems, we plan to systematically study how the notion of time can be appropriately introduced to non-path graph problems (such as temporal covering and temporal coloring problems) and to explore the computational complexity landscape of these new problems. Our over-arching goal is to develop an algorithmic temporal graph theory, similar to the algorithmic graph theory on static graphs, taking into account the inherent presence of the time dimension.

We consider the community of Mobile Computing and Wireless Networks as a potential beneficiary of our research. Due to their nature, wireless networks can often be abstracted as dynamically changing graphs, since the activity and interactions of the devices (e.g. sensors / transmitters / receivers) are inherently influenced by temporal, spatial, and energy constraints. Mobility affects the distance between interacting devices (too long distance implies non-communication and too short distance may imply interference between the transmitted signals), while battery limitations may restrict their activity and the existence or strength of the communication links. Spatial movements of devices can be captured by introducing suitable temporal availability patterns of the edges in a temporal graph. In this context the objectives of a wireless network protocol can be best described via well-adapted temporal analogues of graph optimization problems. Specifically, temporal analogues of covering problems (e.g. vertex cover), conflict problems (e.g. coloring), and path problems (e.g. connectivity) can be used to model continuous surveillance, interference, and information dissemination considerations, respectively. In addition, battery limitations can be expressed by appropriately introducing the notion of ``temporal budget'' within the problem definition. Investigating temporal problems and patterns that more realistically capture inherent properties and practical restrictions of wireless networks, as well as developing efficient algorithms, may result in improved and more efficient wireless network protocols. Implementing such improved protocols in real wireless networks, at a subsequent stage, has the potential to drive economic growth and to impact several application domains in the UK such as mobile communication, transportation, and military.

Further end-beneficiaries include the community of Route Planning in Transportation Networks. The problem of computing optimal routing in real networks is often approached via the problem of computing a shortest path in a graph. Depending on the specific application domain, transportation can be either schedule-based (e.g. public transportation such as buses, trains, and trams), unrestricted (e.g. road networks for cars, walking or cycling), or even multimodal, combining schedule-based means of transportation with less restricted ones. In many cases newly-developed algorithms can answer routing queries in continent-sized road networks within milliseconds, while routing in more complicated multimodal transportation networks still often relies on approximate solutions. The various types of restrictions (e.g. scheduled trains vs. road networks) in different parts of a multimodal network can be expressed by appropriate temporal patterns in a suitably defined temporal graph. The theoretical study of path-related temporal problems may underpin the development of innovative practical algorithms and heuristics for real applications, thus providing a considerable potential for the economy and society due to the wide use of such routing applications from the industry and the public. However, advances in Transportation Route Planning are partially delivered by practitioners and software developers who may have difficulties in transforming theoretical knowledge into applications. Thus, within our pathway towards achieving impact in this area, we consider researchers working at the interface between theory and practice as the immediate beneficiaries of our research. Our main goal will be to disseminate our findings in this community and to interact with them in the direction of identifying the most relevant temporal problems and patterns in routing applications.

Finally, we see our research as promoting and strengthening the area of algorithms and complexity within the UK, thus helping the presence of high quality theoreticians whose research skills will be of interest to the high-tech industry.