在这篇论文中，我们考虑了一个具有有界扩展性的图类 $\text{C}$，以及固定的自然数 $r$ 和 $k$。我们提出了一种动态数据结构，能够在动态图 $G$ 上进行边的插入和删除操作，同时确保在任何时刻 $G \text{ 属于 } \text{C}$。该数据结构能够高效地维护以下两个查询的答案：
- 图 $G$ 是否包含大小为 $k$ 的距离 $r$ 的支配集？
- 图 $G$ 是否包含大小为 $k$ 的距离 $r$ 的独立集？
该数据结构采用随机化方法，错误概率被限制在 $\text{ε}$，其中 $\text{ε}$ 是初始化时固定的参数。其摊销更新时间为 $O(\log^c n \times \log \frac{1}{\text{ε}})$，其中 $n$ 是 $G$ 的顶点数，$c$ 是仅依赖于 $r$、$k$ 和 $\text{C}$ 的常数。在第一个查询的情况下，数据结构还可以输出一个大小为 $k$ 的距离 $r$ 的支配集（如果存在的话）。
我们进一步证明，当 $r=1$ 时，即使仅假设维护的图 $G$ 的退化度被常数 $d$ 限制，该数据结构也能实现支配集查询，进而得到一个更简单的数据结构，摊销更新时间改善为 $O(2^{k^{\text{O}(d)}} \times \log^3 n \times \log \frac{1}{\text{ε}})$。最后，我们证明在退化度最多为 $d$ 的图中，可以维护一个大小为 $O(d^2)$ 的（距离 $1$）支配集的最小大小的近似值，摊销期望更新时间为 $O(d^{\text{O}(1)} \times \log n)$。
博主点评： 本文提出的动态数据结构在稀疏图的支配集与独立集问题上具有重要的理论价值，尤其是在实际应用中，能够有效应对不断变化的图结构，提供高效的查询和更新性能。