k-Efficient domination: Algorithmic perspective.

A set D ⊆ 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 { U 1 , U 2 , ... , U t } such that each U i consists a center vertex u i and all the vertices in distance d i , where d i ∈ { 0 , 1 , ... , k }. In other words, there exist the dominators with various dominating powers. The problem of finding minimum set { u 1 , u 2 , ... , u t } 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. [ABSTRACT FROM AUTHOR]