# Distance domination and amplifier placement problems

We consider an optimisation problem defined on an undirected graph
with a given root vertex and an attenuation 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 amplified spanning tree (AST), is
motivated by local-access television cable networks. We show that
even for planar graphs with no vertex degree exceeding four, for any
s>0 the AST problem is NP-complete. Using connections to so-called
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.

Last modified: Tue Jan 23 15:29:26 EST 2007