论文标题
简单，严格，适当，快乐：暂时图中可及性的研究
Simple, strict, proper, happy: A study of reachability in temporal graphs
论文作者
论文摘要
动态网络是一个复杂的主题。它们不仅继承了静态网络的复杂性（作为特定情况）；它们也对定义的微妙敏感，这是文献中经常引起混淆和无与伦比的无与伦比的来源。 在本文中，我们退后一步，在更多细节中研究了三个这样的方面，以系统的方式探索它们的影响； namely, whether the temporal paths are required to be \emph{strict} (i.e., the times along a path must increasing, not just be non-decreasing), whether the time labeling is \emph{proper} (two adjacent edges cannot be present at the same time) and whether the time labeling is \emph{simple} (an edge can have only one presence time).特别是，我们研究了这些特征的不同组合如何影响图表的表达性。 我们的结果意味着对所得设置的表达性层次结构，阐明了人们在考虑任一组合时所造成的一般性丧失。某些设置比预期的要笼统。特别是，适当的时间图证明与允许非图案路径的一般时间图一样表现力。另外，我们表明，最简单的设置，即\ emph {happy}的时间图（即适当和简单）的表达式足够表达，可以在特定（有限但有用的）意义上模仿一般时间图的可及性。此外，该设置被提倡作为证明负面结果的首选目标。我们通过将两个已知结果加强到快乐图（即稀疏跨度的不存在，以及计算时间分量的硬度）来说明这一点。总体而言，我们希望本文可以将其视为在时间图的不同设置之间进行选择的指南，同时意识到这些选择影响通用性的方式。
Dynamic networks are a complex subject. Not only do they inherit the complexity of static networks (as a particular case); they are also sensitive to definitional subtleties that are a frequent source of confusion and incomparability of results in the literature. In this paper, we take a step back and examine three such aspects in more details, exploring their impact in a systematic way; namely, whether the temporal paths are required to be \emph{strict} (i.e., the times along a path must increasing, not just be non-decreasing), whether the time labeling is \emph{proper} (two adjacent edges cannot be present at the same time) and whether the time labeling is \emph{simple} (an edge can have only one presence time). In particular, we investigate how different combinations of these features impact the expressivity of the graph in terms of reachability. Our results imply a hierarchy of expressivity for the resulting settings, shedding light on the loss of generality that one is making when considering either combination. Some settings are more general than expected; in particular, proper temporal graphs turn out to be as expressive as general temporal graphs where non-strict paths are allowed. Also, we show that the simplest setting, that of \emph{happy} temporal graphs (i.e., both proper and simple) remains expressive enough to emulate the reachability of general temporal graphs in a certain (restricted but useful) sense. Furthermore, this setting is advocated as a target of choice for proving negative results. We illustrates this by strengthening two known results to happy graphs (namely, the inexistence of sparse spanners, and the hardness of computing temporal components). Overall, we hope that this article can be seen as a guide for choosing between different settings of temporal graphs, while being aware of the way these choices affect generality.
