Retraction: Improved Approximation Schemes for Dominating Set Problems in Unit Disk Graphs

Pattara SukprasertarXiv 2021 · arXiv

TL;DR

This paper presents improved approximation schemes for finding minimum dominating sets and minimum connected dominating sets in unit disk graphs. The authors achieve faster running times by employing dynamic programming on grid-based subproblems, a departure from previous brute-force approaches.

What Problem Does This Paper Address?

The paper tackles the problem of finding minimum dominating sets (MDS) and minimum connected dominating sets (MCDS) in unit disk graphs. A dominating set is a subset of vertices in a graph such that every vertex not in the subset is adjacent to at least one vertex in the subset. The goal is to find such a set with the smallest possible number of vertices. Unit disk graphs are a specific type of graph where vertices represent disks of uniform radius in a plane, and an edge exists between two vertices if their corresponding disks overlap. These graphs have applications in areas like wireless sensor networks.

The MDS and MCDS problems are NP-hard in general graphs, and even in unit disk graphs, finding exact solutions is computationally expensive. While approximation algorithms exist, the authors aim to improve the efficiency of existing Polynomial-Time Approximation Schemes (PTAS) for these problems. Specifically, they seek to reduce the dependency on the approximation parameter $\epsilon$ in the running time from $O(1/\epsilon^2)$ or $O(1/\epsilon \log 1/\epsilon)$ to $O(1/\epsilon)$.

Methods

The core of the paper's contribution lies in its novel application of dynamic programming to solve subproblems within a grid-based decomposition of the unit disk graph. The general approach, inspired by previous work, involves dividing the plane into small square cells. The key innovation is how they handle the subproblems within these cells.

Instead of enumerating all possible dominating sets within each cell (which leads to the $O(1/\epsilon^2)$ complexity), the authors leverage structural properties of unit disk graphs. They prove that for optimal solutions, the number of vertices required within a certain region of a cell is bounded by a constant related to the cell's width. This allows them to design dynamic programming algorithms that run in time exponential in the width of the subproblem (which is related to $1/\epsilon$), rather than exponential in $1/\epsilon^2$.

Specifically, they:

  • Grid Decomposition: Divide the plane into cells of a specific size, determined by the approximation parameter $\epsilon$.
  • Dynamic Programming: Develop dynamic programming algorithms to find optimal solutions for subproblems within these cells. This is a significant departure from previous methods that relied on brute-force enumeration of subsets.
  • Connectivity Handling (for MCDS): Adapt the dynamic programming approach to ensure connectivity for the MCDS problem, which adds complexity by requiring states to encode information about connected components.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm design and analysis for unit disk graphs, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Dynamic Programming over Brute Force: The most significant insight is the successful replacement of brute-force enumeration of subsets in subproblems with dynamic programming. This is the key to achieving the improved running times.
  • Bounded Width as a Key Property: The paper highlights that the "bounded width" property of the subproblems (related to the grid cells) is crucial for the efficiency of the dynamic programming approach. This property limits the number of vertices needed to dominate a region.
  • Structural Properties of Unit Disk Graphs: The authors exploit specific geometric and structural properties of unit disk graphs to derive bounds on the number of vertices required in subproblems, which are essential for the DP approach.
  • Unified Framework for MDS and MCDS: The paper demonstrates how a similar dynamic programming framework can be adapted to solve both the MDS and MCDS problems, with the latter requiring additional mechanisms to ensure connectivity.

Key Results

The paper presents improved Polynomial-Time Approximation Schemes (PTAS) for both Minimum Dominating Set (MDS) and Minimum Connected Dominating Set (MCDS) in unit disk graphs.

  • MDS: A PTAS with a running time of $n^{O(1/\epsilon)}$ is presented, improving upon previous algorithms with running times of $n^{O(1/\epsilon \log 1/\epsilon)}$.
  • MCDS: A PTAS with the same improved running time of $n^{O(1/\epsilon)}$ is also presented.

The paper also includes theorems and lemmas that formally establish the correctness and bounds of their algorithms.

Limitations and Future Work

Retraction Note: The paper includes a prominent retraction note stating that the results presented were already known and appeared in Erik Jan van Leeuwen's thesis [vL09]. The techniques used were also found to be similar to other prior work. This significantly undermines the novelty and contribution of the paper.

Acknowledged Limitations (from the original paper before retraction): * Dependency on Geometric Representation: The algorithms rely on the explicit geometric representation of the unit disk graph. * Efficiency for Large $\epsilon$: While the running time is polynomial in $n$, it is exponential in $1/\epsilon$. For very small $\epsilon$, the running time can still be substantial.

Future Work (suggested in the original paper): * Efficient PTAS for MDS: The paper poses an open problem: finding an efficient PTAS for MDS whose running time depends only polynomially in $n$. * Graph-Only Approach: Investigating if the approach can be extended to cases where only the graph structure is given, without the underlying geometric information.

Summary updated

BibTeX
@misc{sukprasert2021retraction,
  author = {Pattara Sukprasert},
  title = {{Retraction: Improved Approximation Schemes for Dominating Set Problems in Unit Disk Graphs}},
  year = {2021},
  eprint = {2109.01283},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2109.01283},
}
Figure