Temporal Cliques Admit Sparse Spanners
Temporal Cliques Admit Sparse Spanners
复制标题
时间派系承认稀疏扳手
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Jason Schoeters
中科院分区：
文献类型：
--
作者：
A. Casteigts;Joseph G. Peters;Jason Schoeters
设${cal G}=（G，lambda）$是n$个顶点的标号图，$lambda：E_G o mathbb{N}$一个局部内射映射，它为每条边分配一个整数标签。当边缘存在时，标签被视为离散时间。这个图是{em时间连通}的，如果存在一条从每个顶点到每个其他顶点的标签递增的路径。在一篇开创性的论文中，Kempe，Kleinberg和Kumar（JCSS 2002）询问，给定这样一个标记图，是否总是可以找到一个边的{em sparse}子集，如果其他边被删除，则保持时间连通性-我们称这样的子集为{em temporal sparse}。最近，Axiotis和Fotakis（ICALP 2016）给出了否定的回答，展示了一族具有$Omega（n^2）$边的最小连通时间图。自然的问题就变成了在特定的稠密图类中是否可以找到稀疏空间。
在这篇文章中，我们解决了完全图的问题{em positively}，表明人们总是可以删除除了$o（n^2）$条边之外的所有边，无论标签是什么，同时保持时间连通性。到目前为止，最好的方法只删除了$O（n）$边，使图的渐近密度不变（Akrida et al.，ToCS 2017）。我们首先观察到，相同的论点可以推广到删除$O（n^2）$边（六分之一的边）。然后，使用一种完全不同的方法，我们建立了一个渐进的结果集，表明四分之一的边缘可以被删除，然后是一半的边缘，最终{em all}但$O（n log n）$边缘。这个结果是强大的意义上说，它延伸，在温和的假设下，更一般的模型的时间集团的标签可能不是本地唯一的，同一个边缘可能有几个标签。现在主要的开放问题是理解在允许稀疏空间的图和不允许稀疏空间的图之间的分离发生在哪里。
Let ${cal G}=(G,lambda)$ be a labeled graph on $n$ vertices with $lambda:E_G o mathbb{N}$ a locally injective mapping that assigns to every edge a single integer label. The label is seen as a discrete time when the edge is present. This graph is {em temporally connected} if a path exists with increasing labels from every vertex to every other vertex. In a seminal paper, Kempe, Kleinberg, and Kumar (JCSS 2002) asked whether, given such a labeled graph, a {em sparse} subset of edges can always be found that preserves temporal connectivity if the other edges are removed -- we call such subsets {em temporal spanners}. Recently, Axiotis and Fotakis (ICALP 2016) answered negatively, exhibiting a family of minimally connected temporal graphs with $Omega(n^2)$ edges. The natural question then becomes whether sparse spanners can be found in specific classes of dense graphs.
In this article, we settle the question {em positively} for complete graphs, showing that one can always remove all but $o(n^2)$ edges, whatever the labels, while preserving temporal connectivity. The best approach so far led to removing only $O(n)$ edges, leaving the asymptotic density of the graph unchanged (Akrida et al., ToCS 2017). We start by observing that the same argument can be generalized to removing $O(n^2)$ edges (a sixth of the edges). Then, using a completely different approach, we establish a gradual set of results, showing that a quarter of the edges can be removed, then half of the edges, and eventually {em all} but $O(n log n)$ edges. This result is robust in the sense that it extends, under mild assumptions, to more general models of temporal cliques where the labels may not be locally unique and a same edge may have several labels. The main open question is now to understand where the separation occurs between graphs that admit sparse spanners and graphs that do not.