Optimal broadcast domination in polynomial time

Broadcast domination was introduced by Erwin in 2002, and it is a variant of the standard dominating set problem, such that different vertices can be assigned different domination powers. Broadcast domination assigns an integer power f(v)⩾0f(v)⩾0 to each vertex vv of a given graph, such that every vertex of the graph is within distance f(v)f(v) from some vertex vv having f(v)⩾1f(v)⩾1. The optimal broadcast domination problem seeks to minimize the sum of the powers assigned to the vertices of the graph. Since the presentation of this problem its computational complexity has been open, and the general belief has been that it might be NP-hard. In this paper, we show that optimal broadcast domination is actually in PP, and we give a polynomial time algorithm for solving the problem on arbitrary graphs, using a non-standard approach.