Exact algorithms for weak Roman domination

We consider the problem. Given an undirected graph , the aim is to find a function (wrd-function for short) of minimum cost, a function such that every vertex is ( there exists a neighbor of , possibly , such that ) and for every vertex with there exists a neighbor of such that and the function defined by , and otherwise does not contain any undefended vertex. The of a wrd-function is defined by . The trivial enumeration algorithm runs in time and polynomial space and is the best one known for the problem so far. We are breaking the trivial enumeration barrier by providing two faster algorithms: we first prove that the problem can be solved in time needing , and then describe an algorithm using . Our results rely on structural properties of a wrd-function, as well as on the best polynomial space algorithm for the problem. Moreover we show that the problem can be solved in linear-time on interval graphs.