(t,r)-Broadcast Domination in graphs

This paper explores a recently introduced graph problem called (t,r)- Broadcast Domination . In this problem, a set of “broadcasting” towers transmit a signal of initial strength t. This signal’s strength decreases linearly along the edges. The objective is to find the smallest set of broadcasting towers such that every vertex in the graph receives a cumulative signal strength of at least r. The (t,r)- Broadcast Domination problem, which generalizes the concept of distance domination, has been recently introduced and studied in a few specific class of graphs, like grids and lattices. However, the (t,r)- Broadcast Domination problem has not been studied for general graphs. We present the first study of the complexity of this problem in general graphs, including a general approximation algorithm and optimal polynomial-time algorithms for cographs. We also provide an algorithm parameterized by the neighborhood diversity of the input graph and an algorithm parameterized by modular-width and the solution size.