# Complexity of finding a spanning tree that minimizes the maximum interference

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.

This problem already is known, and is NP-Hard, but if you like to know more about the interference related problems I'd offer you to read this book.

The Problem 1, in the Buchin work is as follow:

Problem 1 (Locher, von Rickenbach, Wattenhofer[5]). Given n nodes in the plane. Connect the nodes by a spanning tree. For each node v we construct a disk centering 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 defined as the number of disks that include node v (not counting the disk of v itself ). Find a spanning tree that minimizes the maximum interference.

• give some idea about solution. – Manish Kumar May 4 '14 at 0:03