Variants of Domination and Their Algorithmic Complexities

Abstract

The Dominating Set Problem (DSP) is a classical combinatorial optimization problem that aims to find the smallest dominating set (DS) in a given graph G=(V,E). Due to its numerous real-world applications across various domains, such as facility location, social networks, network design, security, and resource allocation, the dominating set and its variants have been extensively studied. In this thesis, we explore several variants of the dominating set, specifically the semi-total dominating set, total dominating set, and total Roman dominating set. All the problems listed here are NP-hard, and none of them admit a constant factor approximation algorithm for general graphs unless P=NP. This challenge motivated us to study these problems within special graph classes.