Given $n$ nodes in the plane, connect the nodes by a spanning tree. For each node $v$ we construct a disk centered at $v$ with radius equal to the distance to $v$’s furthest neighbor in the spanning tree. The interference of a node $v$ is then deﬁned as the number of such disks that include the node $v$.
The problem I'm interested is to find a spanning tree that minimizes the maximum interference.
What is known about the problem in terms of computational complexity? Is it NP-hard? Can it be solved efficiently? What is its inapproximability threshold?
Apparently this problem is still not understood well. I do not know the complexity of the problem (solvable optimally in polynomial time, or NP-complete), and as far as I know it is unknown whether efficient approximation algorithms exist.