k-Efficient domination: Algorithmic perspective

A set D subset of 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) is an element of {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.