Algorithmic Aspects of Temporal Graphs

图上算法的设计和分析是计算机科学的一个主要分支学科。图(由顶点和边组成)不仅在计算机科学和数学中普遍存在，而且在科学和工程的整个范围内都是普遍存在的。它们用于抽象建模不同的现实世界系统，其中顶点和边分别表示基本的系统单元和它们之间的某种交互。然而，在现代系统中，这种使用静态图的建模范例可能会受到限制或过于简化，因为交互通常以高度动态的方式随时间变化。例如，在社交网络中，友谊随时间被添加和移除，并且通信网络中的链接可以根据特定的已知模式(卫星跟踪轨迹)或以不可预测的方式(移动自组织网络)动态地改变。所有这些应用领域的共同特征是系统结构，即图的拓扑结构，随着时间的变化而变化，时态图由一个底层图和一个时间标签函数组成，该函数为图的每条边分配一组离散的时间标签。这些时间标签是从自然数集合中提取的，指示相应边所在的离散时间点。从静态图到时态图的概念转变对基本图参数和度量的定义有重大影响，因此也对可以执行的任务类型产生重大影响。图的性质一般可以分为时态的(即在每个时间点满足)和时态的(即随时间满足的)。例如，尽管全球连通性可能不会在任何单个时间点保持，但随着时间的推移，在每对节点之间仍可能存在通信路径。特别地，当人们沿着路径的边行走时，基础(静态)图G中的路径称为时态的，如果存在递增的时间标签序列。静态图论中的经典度量通常可以通过各种方式推广到时态图中的自然度量。例如，根据应用领域，两个顶点u、v之间的“最短路径”的时间模拟可以被翻译为(A)具有最小边数的拓扑最短路径，(B)具有最小持续时间的最快路径，或(C)尽可能早到达的最前面的路径(与开始时间无关)。静态图问题的计算复杂性可能会也可能不会传递到它的时间对应问题；这在很大程度上取决于问题和相关的度量。众所周知，最短/最快/最前面的时间路径可以在多项式时间内计算；然而，与静态情况相反，在时间图中计算强连通分量是NP-完全的。虽然一些时态图优化问题在最坏的情况下可能很难解决或近似，但当我们在输入时态图中限制(A)其底层拓扑或(B)时间标记，即时间标记出现的时间模式，或两者都限制时，最优解可能是有效的。对输入时态模式的限制是静态图中一个不同的时态特征，在本研究中，我们计划研究各种时态图问题，以及更深入地理解其潜在的组合结构。除了与时间路径相关的问题外，我们还计划系统地研究如何将时间的概念适当地引入非路径图问题(如时间覆盖和时间着色问题)，并探索这些新问题的计算复杂性。我们的总体目标是开发一种算法时态图理论，类似于静态图上的算法图理论，考虑到时间维度的内在存在。

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.