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

Basic Information

• Paper ID: 2501.00207
• Title: Dominating Set, Independent Set, Discrete $k$-Center, Dispersion, and Related Problems for Planar Points in Convex Position
• Authors: Anastasiia Tkachenko, Haitao Wang (University of Utah)
• Classification: cs.CG (Computational Geometry)
• Conference: STACS 2025 (42nd International Symposium on Theoretical Aspects of Computer Science)
• Paper Link: https://arxiv.org/abs/2501.00207

Abstract

This paper investigates several classical computational geometry problems on unit disk graphs under the special setting where points are in convex position. Given a set $P$ of $n$ points in the plane, the unit disk graph $G(P)$ has $P$ as its vertex set, with edges connecting two points if their Euclidean distance is at most 1. Although these problems are NP-hard in general, the authors propose efficient algorithms under the convex position assumption. The problems studied include: finding minimum-weight dominating sets in $G(P)$, discrete $k$-center problems for $P$, finding maximum-weight independent sets in $G(P)$, dispersion problems for $P$, and related variants.

Research Background and Motivation

Problem Significance

1. Unit Disk Graph Model: Has important applications in wireless sensor networks, where connectivity is determined by signal range (unit disk)
2. Classical NP-Hard Problems: Dominating set, independent set, $k$-center, and dispersion are all classical combinatorial optimization problems
3. Convex Position Specificity: When points are in convex position, many originally difficult problems may become tractable

Limitations of Existing Methods

• These problems are NP-hard in general, with only approximation algorithms available
• Previous work lacks systematic study of this special convex position case
• Existing algorithms have high time complexity, such as $O(n^6 \log n)$ for the independent set problem

Research Motivation

To explore whether polynomial-time exact algorithms can be obtained under the convex position assumption and to improve the time complexity of existing algorithms.

Core Contributions

1. Dominating Set Problem:
   • Unweighted case: $O(kn \log n)$ time algorithm (where $k$ is the minimum dominating set size)
   • Weighted case: $O(n^3 \log^2 n)$ time algorithm
2. Discrete $k$-Center Problem:
   • $O(\min\{n^{4/3} \log n + kn \log^2 n, k^2n \log^2 n\})$ time algorithm
   • Worst case: $O(n^2 \log^2 n)$
3. Independent Set Problem:
   • General case: $O(n^{7/2})$ deterministic or $O(n^{37/11})$ randomized expected time algorithm
   • Size-3 case: $O(n \log n)$ algorithm (convex position)
   • Weighted size-3 independent set in arbitrary position: $O(n^{5/3+\delta})$ algorithm
4. Dispersion Problem:
   • General $k$: $O(n^{7/2} \log n)$ deterministic or $O(n^{37/11} \log n)$ randomized algorithm
   • $k=3$: $O(n \log^2 n)$ deterministic or $O(n \log n)$ randomized algorithm

Methodology Details

Problem Definition

• Input: Set $P$ of $n$ points in the plane in convex position
• Unit Disk Graph: Two points in $G(P)$ are connected if and only if their distance is $\leq 1$
• Objective: Solve optimization problems including dominating set, independent set, $k$-center, and dispersion

Core Technical Framework

1. Structural Property Analysis (Dominating Set)

Ordering Property: For an optimal dominating set $S$, there exists an ordering $p_{i_1}, p_{i_2}, \ldots, p_{i_k}$ such that:

• $(p_{i_1}, p_{i_k})$ form a decoupling pair
• Each center is assigned at most two sublists
• Linear separability holds

Key Lemma:

Lemma 5 (Ordering Property): There exists an ordering of centers such that 
the union of sublists of the first t centers forms a contiguous sublist of P, 
satisfying monotonicity and endpoint properties.

2. Dynamic Programming Algorithm

Based on the ordering property, a dynamic programming algorithm is designed:

• State: $f(i,j)$ - maximum weight of points selected in $P(i,j)$ forming an independent set with $\{p_i, p_j\}$
• Transition: Utilize geometric properties of convex position for state transitions
• Complexity: Achieve $O(kn^2 \log^2 n)$ through efficient data structures

3. Parametric Search ($k$-Center Problem)

Employs parametric search technique:

• Simulate decision algorithm on unknown optimal value $r^*$
• Maintain interval $[r_1, r_2)$ containing $r^*$
• Progressively narrow the interval through critical value comparisons
• Apply Cole's technique to optimize to $O(k^2n \log^2 n)$

4. Recursive Structure of Independent Set

Observation 1: For a triangle $\triangle p_i p_j p_k$ in the Delaunay triangulation, its circumcircle contains no other points in the solution, and the Voronoi diagram forms a tree structure.

Recursive Relation: $f(i,j,k) = \max_{p_l \in P_k(p_i,p_j)}(f(i,l,j) + f(l,j,i) + w_l)$

Technical Innovations

1. Geometric Structure Exploitation: Fully utilize geometric properties of convex position, such as tree structure of Voronoi diagrams
2. Cutting Technique: Use hierarchical cuttings to optimize query complexity
3. Tree-Structured Bipartite Clique Partition: First proposed for weighted independent set problems
4. Parametric Search Optimization: Combined with Cole's technique and fractional cascading

Experimental Setup

Theoretical Analysis Framework

This paper primarily conducts theoretical analysis, verifying algorithm correctness through:

1. Complexity Analysis: Detailed time complexity analysis for each algorithm
2. Correctness Proof: Prove algorithm correctness through mathematical induction and proof by contradiction
3. Comparison with Known Results: Compare complexity with existing best algorithms

Comparison Baselines

• Dominating Set: Comparison with general approximation algorithms
• Independent Set: Comparison with Singireddy et al.'s $O(n^6 \log n)$ algorithm
• Dispersion Problem: Comparison with Agarwal et al.'s $O(n^{4/3} \log^2 n)$ algorithm

Experimental Results

Main Results Comparison

Algorithm Performance Analysis

1. Dominating Set Algorithm:
   • Unweighted case achieves $O(kn \log n)$, where $k$ is typically much smaller than $n$
   • Weighted case's $O(n^3 \log^2 n)$ is theoretically the first polynomial-time exact algorithm
2. Independent Set Algorithm:
   • Improved from $O(n^6 \log n)$ to $O(n^{7/2})$, an exponential improvement
   • Randomized algorithm achieves $O(n^{37/11})$ expected time
3. Special Case Optimization:
   • Size-3 independent set problem achieves near-linear time $O(n \log n)$

Related Work

Unit Disk Graph Research

• Clark et al. proved NP-hardness of multiple classical problems on unit disk graphs
• Maximum clique is an exception with polynomial-time algorithm

Convex Position Problems

• Aggarwal et al.'s linear-time Voronoi diagram algorithm
• Choi et al.'s continuous $k$-center algorithm: $O(\min\{k, \log n\} \cdot n^2 \log n + k^2n \log n)$

Dispersion Problems

• Agarwal et al.'s $n^{O(\sqrt{k})}$ time general plane algorithm
• Linear-time algorithms for circular and line cases

Conclusions and Discussion

Main Conclusions

1. Convex position assumption significantly reduces complexity of multiple NP-hard problems
2. Sufficient exploitation of geometric structure is key to algorithm design
3. Effectiveness of parametric search and cutting techniques in geometric optimization

Limitations

1. Restrictive Assumption: Only applicable to point sets in convex position
2. Practical Application: Real-world point sets rarely strictly satisfy convex position
3. Constant Factors: Implicit constants in theoretical analysis may be large

Future Directions

1. Near-Convex Position: Study algorithms when point sets are "close to" convex position
2. Other Geometric Constraints: Explore algorithms under other special geometric configurations
3. Practical Implementation: Convert theoretical algorithms into practically usable implementations

In-Depth Evaluation

Strengths

1. Significant Theoretical Contribution: Multiple problems obtain polynomial-time exact algorithms for the first time
2. Rich Technical Innovation: Introduces new techniques such as tree-structured bipartite clique partition
3. Rigorous Analysis: Detailed complexity analysis and correctness proofs
4. Comprehensive Results: Unified solution for multiple related problems

Weaknesses

1. Limited Applicability: Convex position assumption is quite restrictive
2. Lack of Experimental Validation: Pure theoretical work without practical performance testing
3. Insufficient Constant Factor Analysis: Implicit constants in theoretical complexity may be large

Impact

1. Theoretical Value: Provides new research perspectives for computational geometry and graph algorithms
2. Methodological Contribution: Innovative application of geometric structure analysis and parametric search techniques
3. Future Research: May inspire research on other special geometric configurations

Applicable Scenarios

1. Theoretical Research: Computational geometry and algorithm complexity analysis
2. Special Applications: Sensor networks where nodes are approximately in convex distribution
3. Algorithm Design: Provides inspiration and technical reference for general-case algorithms

References

The paper cites 66 related references covering important works in computational geometry, graph algorithms, wireless networks, and other fields, providing a solid theoretical foundation for the research.

Technical Summary: By deeply analyzing the geometric properties of point sets in convex position, this paper provides efficient exact algorithms for multiple classical NP-hard problems. Although the applicable scope is limited, it has significant value in theoretical contribution and technical innovation, laying a foundation for further research in related fields.