Distance domination and amplifier placement problems

We consider the optimisation problem defined on a connected undirected graph with given root vertex and a parameter s, in which we seek a spanning tree with the smallest number of special (amplifying) vertices such that each vertex in the tree is preceded on its unique path from the root vertex by an amplifying vertex no more than s edges distant. This problem, which we call the amplified spanning tree (AST) problem, is motivated by a practical problem in local access television cable networks. We show that even restricted to planar graphs with no vertex degree exceeding four, AST is NP-complete for every fixed s ≥ 1. Making use of a connection with distance domination problems, we show that two related problems, including total distance domination, are also NP- complete and we derive an approximability upper bound for AST.