## Abstract

For a graph G=(V,E), a set D⊆V is called a semitotal dominating set of G if D is a dominating set of G, and every vertex in D is within distance 2 of another vertex of D. The MINIMUM SEMITOTAL DOMINATION problem is to find a semitotal dominating set of minimum cardinality. Given a graph G and a positive integer k, the SEMITOTAL DOMINATION DECISION problem is to decide whether G has a semitotal dominating set of cardinality at most k. The SEMITOTAL DOMINATION DECISION problem is known to be NP-complete for general graphs. In this paper, we show that the SEMITOTAL DOMINATION DECISION problem remains NP-complete for planar graphs, split graphs and chordal bipartite graphs. We give a polynomial time algorithm to solve the MINIMUM SEMITOTAL DOMINATION problem in interval graphs. We show that the MINIMUM SEMITOTAL DOMINATION problem in a graph with maximum degree Δ admits an approximation algorithm that achieves the approximation ratio of 2+3ln(Δ+1), showing that the problem is in the class log-APX. We also show that the MINIMUM SEMITOTAL DOMINATION problem cannot be approximated within (1−ϵ)ln|V| for any ϵ>0 unless NP ⊆ DTIME (|V| ^{O(loglog|V|)} ). Finally, we prove that the MINIMUM SEMITOTAL DOMINATION problem is APX-complete for bipartite graphs with maximum degree 4.

Original language | English |
---|---|

Pages (from-to) | 46-57 |

Number of pages | 12 |

Journal | Theoretical Computer Science |

Volume | 766 |

DOIs | |

Publication status | Published - 25 Apr 2019 |

## Keywords

- APX-complete
- Approximation algorithm
- Bipartite graphs
- Chordal graphs
- Domination
- Graph algorithm
- Interval graphs
- NP-complete
- Semitotal domination

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science