Weighted efficient domination for P8-free bipartite graphs in polynomial time

A vertex set D in a finite undirected graph G is an efficient dominating set (e.d.s. for short) of G if every vertex of G is dominated by exactly one vertex of D. The Efficient Domination (ED) problem asks for the existence of an e.d.s. in G. The Weighted Efficient Dominating Set (WED for short) problem further asks for an e.d.s. of minimum/maximum weight in a given graph G. ED is known to be NP-complete for P7-free graphs, and even for very restricted Hfree bipartite graph classes such as for K1,4-free bipartite graphs as well as for C4-free bipartite graphs, while it is solvable in polynomial time for P7-free bipartite graphs as well as for S2,2,4-free bipartite graphs. Here we show that (W)ED can be solved in polynomial time for P8-free bipartite graphs. (c) 2025 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).