Paper Info
Title
Global Total K-Domination: Approximation And Hardness Results
Abstract
A subset D subset of V of a graph G = (V, E) is called a global total k-dominating set of G if D is a total k-dominating set of both G and the complement (G) over bar of G. The MINIMUM GLOBAL TOTAL k-DOMINATION problem is to find a global total k-dominating set of minimum cardinality of the input graph G and DECIDE GLOBAL TOTAL k-DOMINATION problem is the decision version of MINIMUM GLOBAL TOTAL k-DOMINATION problem. The DECIDE GLOBAL TOTAL k-DOMINATION problem is known to be NP-complete for general graphs as well as for bipartite graphs. In this paper, we strengthen the NP-completeness result of DECIDE GLOBAL TOTAL k-DOMINATION problem by showing that this problem remains NP-complete for perfect elimination bipartite graphs, star-convex bipartite graphs and doubly chordal graphs. On the positive side, we give a polynomial time algorithm for the MINIMUM GLOBAL TOTAL k-DOMINATION problem for chordal bipartite graphs, which is a subclass of bipartite graphs. We propose a 2(1 +ln vertical bar V vertical bar)-approximation algorithm for the MINIMUM GLOBAL TOTAL k-DOMINATION problem for any graph. We show that MINIMUM GLOBAL TOTAL k-DOMINATION problem cannot be approximated within (1 - epsilon)ln vertical bar V vertical bar for any epsilon > 0 unless P = NP for any integer k >= 1. We further show that for bipartite graphs, MINIMUM GLOBAL TOTAL k DOMINATION problem cannot be approximated within (1/6 - c)ln vertical bar V vertical bar for any epsilon > 0 unless P = NP for any k >= 1. Finally, we show that the MINIMUM GLOBAL TOTAL k-DOMINATION problem is APX-complete for bounded degree bipartite graphs for any fixed integer k >= 1. (C) 2020 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2021
10.1016/j.tcs.2020.10.027
THEORETICAL COMPUTER SCIENCE
Keywords
DocType
Volume
Domination, Polynomial time algorithm, NP-complete, APX-complete, Graph algorithm
Journal
850
ISSN
Citations 
PageRank 
0304-3975
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
B. S. Panda19921.18
Pooja Goyal201.35