论文标题
可达性的动态复杂性：我们可以处理多少个更改？
Dynamic complexity of Reachability: How many changes can we handle?
论文作者
论文摘要
在2015年，显示任意定向图的可及性能在插入或删除单个边缘后通过一阶公式更新。后来，在2018年，它扩展了大小$ \ frac {\ log n} {\ log \ log n} $的更改，其中$ n $是图形的大小。当还可以使用大多数量化器时，可以处理各种大小的变化。 在本文中，我们通过表明，对于多毛体大小的变化，一阶更新公式的变化足以维持（1）无方向的可及性，以及（2）插入下的定向可及性。对于有效平行算法可以计算非零循环权重的有向图的类别，可以使用更新公式来维持可及性，这些公式可以在多组矩阵大小的变化下使用“ Modulo 2”量化器。这些类的示例包括具有有界树宽的平面图和图形类别。后者在这里显示。 由于我们认为的逻辑无法在更大尺寸的变化下保持可及性，因此相对于变化的大小，我们的结果是最佳的。
In 2015, it was shown that reachability for arbitrary directed graphs can be updated by first-order formulas after inserting or deleting single edges. Later, in 2018, this was extended for changes of size $\frac{\log n}{\log \log n}$, where $n$ is the size of the graph. Changes of polylogarithmic size can be handled when also majority quantifiers may be used. In this paper we extend these results by showing that, for changes of polylogarithmic size, first-order update formulas suffice for maintaining (1) undirected reachability, and (2) directed reachability under insertions. For classes of directed graphs for which efficient parallel algorithms can compute non-zero circulation weights, reachability can be maintained with update formulas that may use "modulo 2" quantifiers under changes of polylogarithmic size. Examples for these classes include the class of planar graphs and graphs with bounded treewidth. The latter is shown here. As the logics we consider cannot maintain reachability under changes of larger sizes, our results are optimal with respect to the size of the changes.
