Semitotal domination in unit disk graphs

Technical Summary: Semitotal Domination in Unit Disk Graphs

Problem Definition
The paper addresses the Minimum Semitotal Domination problem on Unit Disk Graphs (UDGs). A set $S \subseteq V$ is defined as a semitotal dominating set (STDS) of a graph $G=(V, E)$ if it satisfies two conditions:

1. Dominating Condition: Every vertex in $V \setminus S$ is adjacent to at least one vertex in $S$.
2. Semitotal Condition: Every vertex in $S$ is within distance 2 of another vertex in $S$.

The objective is to find an STDS with the minimum cardinality, denoted as the semitotal domination number $\gamma_{t2}(G)$. The decision version of this problem is known to be NP-complete for UDGs. The paper operates under the graph-based input model, where the graph is provided via its adjacency structure, and explicit geometric coordinates are not available, though the graph is guaranteed to be a UDG.

Methodology
The authors propose a deterministic 5-factor approximation algorithm (Algorithm 1) that constructs a maximal independent set (MIS) satisfying the semitotal condition. The methodology relies on the following structural approach:

1. Breadth-First-Search (BFS) Layering: The algorithm selects an arbitrary root $r$ and constructs a BFS tree ($T_{BFS}$). The vertex set $V$ is partitioned into layers $L_0, L_1, \dots, L_R$, where $L_i$ contains vertices at distance $i$ from the root.
2. Greedy Construction:
   • The algorithm initializes the solution set $S$ with the root $r$.
   • It processes layers in non-decreasing order ($i$ from 2 to $R$).
   • For each layer, it iteratively selects a vertex $v$ from the remaining un-dominated vertices in that layer, adds $v$ to $S$, and removes the closed neighborhood of $v$ from the candidate set.
   • This process continues until all vertices are either in $S$ or dominated by $S$.
3. Special Case Handling: If the maximum distance $R=1$, the algorithm selects the root and any single neighbor, which is proven to be optimal.

Key Contributions and Results

• Approximation Guarantee: The paper proves that the size of the set $S$ returned by the algorithm satisfies $|S| \le 5 \cdot \gamma_{t2}(G)$. This is achieved by leveraging a known lemma stating that for any UDG, the size of a maximal independent set is at most 5 times the domination number $\gamma(G)$. Since $\gamma(G) \le \gamma_{t2}(G)$, the 5-approximation holds.
• Correctness: The authors demonstrate that the constructed set $S$ is not only a maximal independent set (and thus a dominating set) but also satisfies the semitotal condition. Specifically, the layer-wise processing ensures that every selected vertex has a "partner" within distance 2 (either the root for vertices in $L_2$, or a vertex in the same or previous layer for vertices in $L_i$ where $i \ge 3$).
• Time Complexity: The algorithm runs in $O(n + m)$ time, where $n$ is the number of vertices and $m$ is the number of edges. In the worst case, this is $O(n^2)$.

Significance and Claims
The paper claims to improve upon the state-of-the-art for the Minimum Semitotal Domination problem in UDGs under the graph-based input model. Specifically:

• It improves the approximation factor from 5.75 (previously achieved by Henning et al.) to 5.
• It improves the running time from $O(n^3)$ to $O(n+m)$.
• The work provides a more efficient and tighter approximation bound for this NP-complete problem without requiring geometric coordinates, making it suitable for scenarios where only graph connectivity is known.

The authors note that while the problem is NP-complete for general graphs and restricted classes (planar, split, chordal bipartite), and previously solved with a 6-factor approximation in geometric models, this work offers the best known deterministic approximation for the graph-based model.