Polynomial-time algorithm for weighted efficient domination problem on diameter three planar graphs

A set D of vertices in a graph G is an efficient dominating set (e.d.s. for short) of G if D is an independent set and every vertex not in D is adjacent to exactly one vertex in D. The efficient domination (ED) problem asks for the existence of an e.d.s. in G. The minimum weighted efficient domination problem (MIN-WED for short) is the problem of finding an e.d.s. of minimum weight in a given vertex-weighted graph. Brandstadt, Ficur, Leitert and Milanic (2015) [3] stated the running times of the fastest known polynomial-time algorithms for the MIN-WED problem on some graphs classes by using a Hasse diagram. In this paper, we update this Hasse diagram by showing that, while for every integer d such that d = 3k or d = 3k + 2, where k >= 1, the ED problem remains NP-complete for graphs of diameter d, the weighted version of the problem is solvable in time O(vertical bar V(G)vertical bar + vertical bar E(G)vertical bar) in the class of diameter three bipartite graphs and in time O(vertical bar V(G)vertical bar(5)) in the class of diameter three planar graphs. (C) 2018 Elsevier B.V. All rights reserved.