K-Efficient domination: Algorithmic perspective

Abstract

A set D a V of a graph G = (V,E) is called an efficient dominating set of G if every vertex v has exactly one neighbor in D, in other words, the vertex set V is partitioned to some circles with radius one such that the vertices in D are the centers of partitions. A generalization of this concept, introduced by Chellali et al. [k-Efficient partitions of graphs, Commun. Comb. Optim. 4 (2019) 109-122], is called k-efficient dominating set that briefly partitions the vertices of graph with different radiuses. It leads to a partition set {U1,U2,..,Ut} such that each Ui consists a center vertex ui and all the vertices in distance di, where di {0, 1,..,k}. In other words, there exist the dominators with various dominating powers. The problem of finding minimum set {u1,u2,..,ut} is called the minimum k-efficient domination problem. Given a positive integer S and a graph G = (V,E), the k-efficient Domination Decision problem is to decide whether G has a k-efficient dominating set of cardinality at most S. The k-efficient Domination Decision problem is known to be NP-complete even for bipartite graphs [M. Chellali, T. W. Haynes and S. Hedetniemi, k-Efficient partitions of graphs, Commun. Comb. Optim. 4 (2019) 109-122]. Clearly, every graph has a k-efficient dominating set but it is not correct for efficient dominating set. In this paper, we study the following: k-efficient domination problem set is NP-complete even in chordal graphs. A polynomial-Time algorithm for k-efficient domination in trees. k-efficient domination on sparse graphs from the parametrized complexity perspective. In particular, we show that it is W[1]-hard on d-degenerate graphs while the original dominating set has Fixed Parameter Tractable (FPT) algorithm on d-degenerate graphs. k-efficient domination on nowhere-dense graphs is FPT. © 2022 World Scientific Publishing Company.