Keywords Semitotal dominating set, Approximation algorithm, Unit disk graph

05C69, 68W25

1 Introduction↩︎

In this paper, we consider only simple undirected connected graphs with at least two vertices. For standard graph-theoretical notation and terminology, we refer the reader to [1]. Let \(G=(V,E)\) be a graph with \(n=|V|\) vertices and \(m=|E|\) edges. For a vertex \(v\in V\), let \(N(v)=\{ u\in V: uv\in E\}\) and \(N[v]=N(v)\cup \{ v\}\) denote its open and closed neighborhoods, respectively. The degree of vertex \(v \in V\) is \(d(v) = |N(v)|\). For \(S\subseteq V\), let \(N(S)\) denote the neighbor set of vertices in \(S\). For vertices \(u, v \in V\), the distance between them in \(G\) is denoted by \(d(u, v)\).

A set \(I\subseteq V\) is called an independent set (IS) of \(G\) if all vertices in \(I\) are pairwise non-adjacent, and it is further called a maximal independent set (MIS) if each vertex \(V\setminus I\) is adjacent to at least one vertex in \(I\).

A set \(D \subseteq V\) is called a dominating set (DS) of \(G\) if every vertex in \(V \setminus D\) is adjacent to at least one vertex in \(D\). The minimum cardinality of a dominating set is the domination number \(\gamma(G)\). A DS is called a total dominating set (TDS) if it also induces a subgraph with no isolated vertex. The minimum cardinality of a total dominating set is the total domination number \(\gamma_t(G)\).

A set \(S \subseteq V\) is called a semitotal dominating set (STDS) of \(G\) if it is a dominating set and every vertex in \(S\) is within distance 2 of another vertex in \(S\). The minimum cardinality of such a set is the semitotal domination number \(\gamma_{t2}(G)\).

Clearly, every semitotal dominating set is also a dominating set, and every total dominating set is a semitotal dominating set. Consequently, the semitotal domination number of a connected graph \(G\) with \(n\geq 2\) satisfies \(\gamma(G) \leq \gamma_{t2}(G) \leq \gamma_t(G)\).

A graph \(G\) is a unit disk graph (UDG) if there exists a mapping \(p : V \to \mathbb{R}^2\) such that, for all distinct vertices \(u, v \in V\), \(uv \in E \text{ if and only if } \| p(u) - p(v) \|_2 \leq 1\). This normalized point-distance definition is equivalent, after scaling, to representing the graph as the intersection graph of congruent disks. Unit disk graphs are widely used to model wireless and mobile networks.

The Minimum Semitotal Domination problem asks for a semitotal dominating set of minimum cardinality. The decision version is NP-complete for unit disk graphs [2]. In the graph-based input model, the graph is supplied by its adjacency structure and is guaranteed to be a UDG; explicit geometric coordinates are not available.

Our contribution is a deterministic \(5\)-approximation algorithm in the graph-based input model. The algorithm constructs a maximal independent set by processing breadth-first-search layers in nondecreasing order. A key feature of this ordering is that every selected vertex has a selected partner at distance two. With adjacency-list input, the algorithm runs in \(O(n + m)\) time.

2 Related work↩︎

In computational complexity theory, the dominating set problem is a classical NP-complete problem. The domination problem and its variations have been extensively studied in the literature. For a comprehensive survey on these topics, see the book [3].

The concept of the semitotal dominating set was introduced by Goddard et al.[4] in 2014. The authors in [4] established that for any connected graph \(G\) with \(n \geq 4\) vertices, the semitotal domination number satisfies \(\gamma_{t2}(G) \leq \frac{n}{2}\). Additionally, they showed that if \(G\) is a graph with \(n\) vertices and maximum degree \(\Delta\), then \(\gamma_{t2}(G) \geq \frac{2n}{2\Delta+1}\). The Semitotal Domination Decision problem is NP-complete for general graphs [4] and remains NP-complete for several restricted graph classes, including planar graphs, split graphs, and chordal bipartite graphs [5].

On the algorithmic side, minimum semitotal dominating sets can be found in linear time in trees [4], [6] and block graphs [7]. A polynomial-time algorithm is known for interval graphs [5], and a linear-time algorithm is available for strongly chordal graphs [8].

Recently, Rout and Das [2] demonstrated that the problem is also NP-complete for unit disk graphs and proposed a 6-factor approximation algorithm with \(O(n \log n)\) running time under a geometric input model. Henning et al. [9] subsequently obtained a \(5.75\)-approximation algorithm with \(O(n^3)\) running time in the graph-based input model. The algorithm presented below improves both the approximation guarantee and the running time in the latter model.

3 The approximation algorithm↩︎

Our algorithm’s approximation guarantee relies on the relationship between the size of an MIS and the minimum cardinality of a dominating set in UDGs. The following lemma will be used in our performance analysis.

Lemma 1 [10]. For any UDG \(G\), if \(I\) is a maximal independent set, then \(|I| \leq 5 \cdot \gamma(G)\).

A tree is an acyclic connected graph. A Breadth-First-Search (BFS) tree is a spanning tree constructed by breadth-first search. It stores the shortest paths from a starting vertex to all other vertices in an unweighted graph, with vertices organized layer by layer according to their distance from the source. Every vertex except the root has exactly one parent vertex via which it is first visited. The collection of all these parent-child edges forms the BFS tree.

Given a graph \(G=(V,E)\), select a vertex \(r\in V\). Denote by \(T_{\text{BFS}}\) the BFS tree rooted at \(r\) in \(G\). Let \(d(r,v)\) denote the distance from vertex \(v\) to the root \(r\) in \(T_{\text{BFS}}\). After fixing the root \(r\), the maximum distance from \(r\) to all other vertices can be easily computed, denoted as \(R\). For each integer \(0\leq i\leq R\), define the \(i\)-th layer of \(T_{\text{BFS}}\) as \(L_i = \{v\in V \mid d(r,v)=i\}\). The family \(\{L_0,L_1,\dots,L_R\}\) forms a partition of the vertex set \(V\), and every vertex in \(L_i\) has a parent in \(L_{i-1}\), \(1\leq i\leq R\). Obviously, \(L_0 = \{r\}\), \(L_1 = N(r)\).

An illustrative example with \(T_{\text{BFS}}=3\) is given in Figure 1. The MIS consists of vertex \(r\) and five black vertices; four grey nodes are their parent vertices.

It is well-known that any maximal independent set is a dominating set. In fact, the maximal independent set obtained via a specific construction method can also be a semitotal dominating set. We now use a greedy algorithm to find a maximal independent set \(S\). The algorithm begins with the root. It then scans the remaining layers in increasing order. Whenever an vertex is encountered, the vertex is added to the solution and its closed neighborhood is deleted. The only exceptional case is \(R=1\), in which the root together with any one of its neighbors is then optimal.

If \(R=1\), choose any vertex \(x\in L_1\) and set \(S=\{r, x\}\). The set \(S\) is a semitotal dominating set. Every semitotal dominating set has at least two vertices, so \(S\) is optimal in this case. In the following, we assume \(R\geq 2\). The algorithm is more formally presented as follows.

Layer-wise semitotal domination

Input: A connected UDG \(G\), a root \(r\), and its BFS layers \(L_1,L_2,\dots,L_R\)
Output: Maximal independent set \(S\)

1. set \(S := \{r\}\); \(V' := V \setminus N_G[r]\)

2. for \(i:=2\) to \(R\)

3. \(L_i \cap V' \neq \emptyset\)

4. Choose a vertex \(v\in L_i\cap V'\)

5. \(S:=S\cup \{v\}\)

6. \(V':=V'\setminus N_G[v]\)

7. end while

8. end for

9. return \(S\)

Theorem 2 Let \(G = (V,E)\) be a unit disk graph. The set \(S\) returned by Algorithm 1 is a semitotal dominating set, and \(|S|\leq 5 \cdot\gamma_{t2}(G)\). The algorithm runs in \(O(m+n)\) time.

Proof. Whenever a vertex is added to \(S\), its closed neighborhood is delected. Hence no subsequently selected vertex is adjacent to it, and \(S\) is independent. The root \(r\) dominates \(L_0\cup L_1\). Every vertex in a later layer is either selected when it is scanned or has already been deleted by a selected neighbor. Thus \(S\) dominates \(G\). Therefore \(S\) is a maximal independent set.

It remains to verify the semitotal condition. Since \(R \ge 2\), the layer \(L_2\) is nonempty, at least one vertex \(x \in L_2\) is selected. Consequently, \(d(r, x) = 2\), and the root has a partner in \(S\).

Now let \(u \in S \cap L_i\) for some \(i \ge 2\), and let \(w \in L_{i-1}\) be the parent of \(u\) in the BFS tree. If \(i = 2\), then \(w \in L_1\) is adjacent to \(r\), and hence \(d(u, r) = 2\). Suppose that \(i \ge 3\). The layer \(L_{i-1}\) was completely processed before \(u\) was selected. The parent \(w\) cannot belong to \(S\), because then selecting \(w\) would delete \(u\). Hence \(w\) must be adjacent to some vertex \(v\in S\) in the same layer or the previous layer, which implies \(d(u,v)=2\). Thus every vertex in \(S\) has another vertex of \(S\) within distance two. In addition, any maximal independent set is also a dominating set, so \(S\) is a semitotal dominating set. By Lemma 1 and the inequality \(\gamma(G)\leq \gamma_{t2}(G)\), we have \(|S| \leq 5\cdot\gamma(G)\leq 5 \cdot\gamma_{t2}(G)\). Thus the approximation factor is at most 5.

Constructing BFS tree and computing a maximal independent set \(S\) by the greedy algorithm both take \(O(m+n)\) time. Hence, the total time complexity is \(O(m+n)\), which is \(O(n^2)\) in the worst case. This completes the proof. \(\square\)

Acknowledgements↩︎

This work is supported by the National Natural Science Foundation of China under grant number 12571381.

References↩︎