Exact Algorithms for Weak Roman Domination

摘要

We consider the Weak Roman Domination problem. Given an undirected graph G = (V, E), the aim is to find a weak ro-man domination function (wrd-function for short) of minimum cost, i.e. a function f : V → {0,1,2} such that every vertex v ∈ V is defended (i.e. there exists a neighbor u of v, possibly u = v, such that f(u) ≥ 1) and for every vertex v ∈ V with f(v) = 0 there exists a neighbor u of v such that f(u) ≥ 1 and the function f_(u→v) defined by: f_(u→v)(x)=｛1 if x=v f(u) - 1 if x = u f(x) if x in not an element of {u,v} does not contain any undefended vertex. The cost of a wrd-function f is defined by cost(f) = ∑_(v∈V) f(v). The trivial enumeration algorithm runs in time O~*(3~n) 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 O~*(2~n) time needing exponential space, and then describe an O~* (2.2279~n) algorithm using polynomial space. Our results rely on structural properties of a wrd-function, as well as on the best polynomial space algorithm for the Red-Blue Dominating Set problem.