Axioms, Vol. 12, Pages 506: An Approximation Algorithm for a Variant of Dominating Set Problem

Axioms, Vol. 12, Pages 506: An Approximation Algorithm for a Variant of Dominating Set Problem

Axioms doi: 10.3390/axioms12060506

Authors: Limin Wang Wenqi Wang

In this paper, we consider a variant of dominating set problem, i.e., the total dominating set problem. Given an undirected graph G=(V,E), a subset of vertices T⊆V is called a total dominating set if every vertex in V is adjacent to at least one vertex in T. Based on LP relaxation techniques, this paper gives a distributed approximation algorithm for the total dominating set problem in general graphs. The presented algorithm obtains a fractional total dominating set that is, at most, k(1+Δ1k)Δ1k times the size of the optimal solution to this problem, where k is a positive integer and Δ is the maximum degree of G. The running time of this algorithm is constant communication rounds under the assumption of a synchronous communication model.