Hardness and Approximation Results on the Total Dominating Set Problem

Publications

Hardness and Approximation Results on the Total Dominating Set Problem

Author : Ms Sasmita Rout

Year : 2026

Publisher : Springer Science and Business Media Deutschland GmbH

Source Title : Lecture Notes in Computer Science

Document Type :

Abstract

Let G=(V,E) be a simple undirected graph with no isolated vertex. A set Dt⊆V is a total dominating set of G if (i) Dt is a dominating set, and (ii) the set Dt induces a subgraph with no isolated vertex. The total dominating set of the minimum cardinality is called the minimum total dominating set, and the size of the minimum total dominating set is called the total domination number (γt(G)). Given a graph G, the total dominating set (TDS) problem is to find a total dominating set of minimum cardinality. In this paper, we enhance the hardness of the TDS problem by proving that it is NP-complete on grid-aligned UDGs, a subclass of unit disk graphs (UDGs). Furthermore, we present a 6.29 factor approximation algorithm for the TDS problem in UDGs.