2025-11-22T05:28:16.205284

Dominating Set, Independent Set, Discrete $k$-Center, Dispersion, and Related Problems for Planar Points in Convex Position

Tkachenko, Wang

Given a set $P$ of $n$ points in the plane, its unit-disk graph $G(P)$ is a graph with $P$ as its vertex set such that two points of $P$ are connected by an edge if their (Euclidean) distance is at most $1$. We consider several classical problems on $G(P)$ in a special setting when points of $P$ are in convex position. These problems are all NP-hard in the general case. We present efficient algorithms for these problems under the convex position assumption. The considered problems include the following: finding a minimum weight dominating set in $G(P)$, the discrete $k$-center problem for $P$, finding a maximum weight independent set in $G(P)$, the dispersion problem for $P$, and several of their variations. For some of these problems, our algorithms improve the previously best results, while for others, our results provide first-known solutions.

academic

基本信息

论文ID: 2501.00207
标题: Dominating Set, Independent Set, Discrete $k$ -Center, Dispersion, and Related Problems for Planar Points in Convex Position
作者: Anastasiia Tkachenko, Haitao Wang (University of Utah)
分类: cs.CG (Computational Geometry)
发表会议: STACS 2025 (42nd International Symposium on Theoretical Aspects of Computer Science)
论文链接: https://arxiv.org/abs/2501.00207

单位圆盘图模型：在无线传感器网络中具有重要应用，其中连通性由信号范围（单位圆盘）决定
经典NP困难问题：支配集、独立集、 $k$ -中心、分散等问题都是经典的组合优化问题
凸位置的特殊性：点集处于凸位置时，许多原本困难的问题可能变得可处理

现有方法局限性

一般情况下这些问题都是NP困难的，只有近似算法
对于凸位置这一特殊情况，之前缺乏系统性研究
现有算法时间复杂度较高，如独立集问题的 $O(n^6 \log n)$ 算法

研究动机

探索凸位置假设下是否能获得多项式时间的精确算法，并改进现有算法的时间复杂度。

核心贡献

支配集问题：
- 无权情况： $O(kn \log n)$ 时间算法（ $k$ 为最小支配集大小）
- 有权情况： $O(n^3 \log^2 n)$ 时间算法
离散 $k$ -中心问题：
- $O(\min\{n^{4/3} \log n + kn \log^2 n, k^2n \log^2 n\})$ 时间算法
- 最坏情况下为 $O(n^2 \log^2 n)$
独立集问题：
- 一般情况： $O(n^{7/2})$ 确定性算法或 $O(n^{37/11})$ 随机期望算法
- 大小为3的情况： $O(n \log n)$ 算法（凸位置）
- 任意位置的加权大小3独立集： $O(n^{5/3+\delta})$ 算法
分散问题：
- 一般 $k$ ： $O(n^{7/2} \log n)$ 确定性或 $O(n^{37/11} \log n)$ 随机算法
- $k=3$ ： $O(n \log^2 n)$ 确定性或 $O(n \log n)$ 随机算法

方法详解

任务定义

输入：平面上 $n$ 个点的集合 $P$ ，处于凸位置
单位圆盘图： $G(P)$ 中两点相连当且仅当距离 $\leq 1$
目标：解决支配集、独立集、 $k$ -中心、分散等优化问题

核心技术框架

1. 结构性质分析（支配集）

排序性质（Ordering Property）：对于最优支配集 $S$ ，存在一个排序 $p_{i_1}, p_{i_2}, \ldots, p_{i_k}$ 使得：

$(p_{i_1}, p_{i_k})$ 构成解耦对
每个中心最多分配两个子列表
具有线可分性

关键引理：

引理5（排序性质）：存在中心的排序，使得前t个中心的子列表并集形成P的连续子列表，且满足单调性和端点性质。

2. 动态规划算法

基于排序性质，设计动态规划：

状态： $f(i,j)$ - 在 $P(i,j)$ 中选择点使得与 $\{p_i, p_j\}$ 构成独立集的最大权重
转移：利用凸位置的几何性质进行状态转移
复杂度：通过高效的数据结构实现 $O(kn^2 \log^2 n)$

3. 参数搜索（ $k$ -中心问题）

使用参数搜索技术：

模拟决策算法在未知最优值 $r^*$ 上的运行
维护包含 $r^*$ 的区间 $[r_1, r_2)$
通过关键值比较逐步缩小区间
应用Cole技术优化到 $O(k^2n \log^2 n)$

4. 独立集的递归结构

观察1：对于Delaunay三角剖分中的三角形 $\triangle p_i p_j p_k$ ，其外接圆不包含其他解中的点，且Voronoi图形成树结构。

递归关系： $f(i,j,k) = \max_{p_l \in P_k(p_i,p_j)}(f(i,l,j) + f(l,j,i) + w_l)$

技术创新点

几何结构利用：充分利用凸位置的几何性质，如Voronoi图的树结构
切割技术：使用hierarchical cuttings优化查询复杂度
树结构二部团划分：首次提出用于加权独立集问题
参数搜索优化：结合Cole技术和分数级联

实验设置

理论分析框架

本文主要进行理论分析，通过以下方式验证算法正确性：

复杂度分析：详细分析每个算法的时间复杂度
正确性证明：通过数学归纳和反证法证明算法正确性
与已知结果比较：与现有最佳算法进行复杂度对比

对比基准

支配集：与一般近似算法比较
独立集：与Singireddy等人的 $O(n^6 \log n)$ 算法比较
分散问题：与Agarwal等人的 $O(n^{4/3} \log^2 n)$ 算法比较

实验结果

主要结果对比

问题	本文结果	之前最佳结果	改进
无权支配集	$O(kn \log n)$	-	首个结果
有权支配集	$O(n^3 \log^2 n)$	-	首个结果
独立集（一般）	$O(n^{7/2})$	$O(n^6 \log n)$	显著改进
独立集（大小3）	$O(n \log n)$	$O(n^{4/3} \log^2 n)$	显著改进
分散（ $k=3$ ）	$O(n \log^2 n)$	$O(n^{4/3} \log^2 n)$	改进

算法性能分析

支配集算法：
- 无权情况达到 $O(kn \log n)$ ，其中 $k$ 通常远小于 $n$
- 有权情况的 $O(n^3 \log^2 n)$ 在理论上是首个多项式时间精确算法
独立集算法：
- 从 $O(n^6 \log n)$ 改进到 $O(n^{7/2})$ ，指数级改进
- 随机算法达到 $O(n^{37/11})$ 期望时间
特殊情况优化：
- 大小为3的独立集问题达到近线性时间 $O(n \log n)$