Semitotal domination in unit disk graphs

技术摘要：单位圆盘图中的半全支配问题

问题定义
本文研究了**单位圆盘图（Unit Disk Graphs, UDGs）上的最小半全支配（Minimum Semitotal Domination）*问题。对于图 $G=(V, E)$，集合 $S \subseteq V$ 被定义为一个半全支配集*（semitotal dominating set, STDS），需满足以下两个条件：

1. 支配条件： $V \setminus S$ 中的每个顶点都至少与 $S$ 中的一个顶点相邻。
2. 半全条件： $S$ 中的每个顶点与 $S$ 中的另一个顶点的距离在 2 以内。

目标是找到一个具有最小基数的 STDS，记作 $\gamma_{t2}(G)$。该问题的判定版本在 UDGs 中已被证明是 NP 完全的。本文在基于图的输入模型下运行，即通过图的邻接结构提供输入，而不提供显式的几何坐标，尽管该图保证是一个 UDG。

方法论
作者提出了一种确定性的 5 倍近似算法（算法 1），该算法构造了一个满足半全条件的极大独立集（MIS）。其方法论依赖于以下结构化方法：

1. 广度优先搜索（BFS）分层： 算法选择一个任意根节点 $r$，并构建一棵 BFS 树（$T_{BFS}$）。顶点集 $V$ 被划分为层 $L_0, L_1, \dots, L_R$，其中 $L_i$ 包含距离根节点距离为 $i$ 的顶点。
2. 贪心构造：
   • 算法将初始解集 $S$ 设置为根节点 $r$。
   • 算法按非递减顺序处理各层（$i$ 从 2 到 $R$）。
   • 对于每一层，算法迭代地从该层剩余的未被支配顶点中选择一个顶点 $v$，将其加入 $S$，并将 $v$ 的闭邻域从候选集中移除。
   • 此过程持续进行，直到所有顶点要么属于 $S$，要么被 $S$ 支配。
3. 特殊情况处理： 如果最大距离 $R=1$，算法选择根节点及任何一个邻居，这被证明是最优的。

主要贡献与结果

• 近似保证： 文中证明了算法返回的集合 $S$ 满足 $|S| \le 5 \cdot \gamma_{t2}(G)$。这是通过利用一个已知引理实现的：对于任何 UDG，极大独立集的大小至多是支配数 $\gamma(G)$ 的 5 倍。由于 $\gamma(G) \le \gamma_{t2}(G)$，因此 5 倍近似成立。
• 正确性： 作者证明了所构造的集合 $S$ 不仅是一个极大独立集（因此也是一个支配集），而且还满足半全条件。具体而言，逐层处理的过程确保了每个选中的顶点都有一个“伙伴”在距离 2 之内（对于 $L_2$ 中的顶点，其伙伴是根节点；对于 $i \ge 3$ 的 $L_i$ 中的顶点，其伙伴在同一层或前一层中）。
• 时间复杂度： 该算法的运行时间为 $O(n + m)$，其中 $n$ 是顶点数，$m$ 是边数。在最坏情况下，为 $O(n^2)$。

意义与主张
本文声称改进了在基于图的输入模型下，针对单位圆盘图中最小半全支配问题的现有技术水平。具体而言：

• 将近似因子从 5.75（此前由 Henning 等人实现）提升至 5。
• 将运行时间从 $O(n^3)$ 优化至 $O(n+m)$。
• 这项工作为这个 NP 完全问题提供了一个更高效且近似界限更紧的确定性算法，且无需几何坐标，使其适用于仅已知图连通性的场景。

作者指出，虽然该问题对于一般图以及受限类图（平面图、分裂图、弦二部图）都是 NP 完全的，且此前在几何模型中以 6 倍近似解决，但本研究为基于图的模型提供了目前已知的最佳确定性近似算法。