2026/07/16 by Mingjun Liu, Weiping Shang
#cs.DS #cs.DM #math.CO
A set S ⊆ V is called a \em semitotal dominating set of G=(V,E) if every vertex in V ∖ S is adjacent to at least one vertex in S, and every vertex in S is within distance 2 of another vertex in S. The corresponding decision problem is NP-complete even for unit disk graphs. In this paper, we present a 5-factor approximation algorithm for the Minimum Semitotal Domination problem on unit disk graphs in the graph-based input model. The algorithm processes the layers of a Breadth-First-Search tree and constructs a maximal independent set whose vertices satisfy the semitotal condition. For a graph with n vertices and m edges, the algorithm runs in O(n + m) time, and hence in O(n2) time in the worst case. This improves the previously known 5.75-approximation algorithm with O(n3) running time.