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.