On the Hardness of Range Assignment Problems

We investigate the computational hardness of the connectivity,the strong connectivity, and the broadcast type of range assignmentproblems in ℝ2 and ℝ3. We presentnew reductions for the connectivity problem, which are easilyadapted to suit the other two problems. All reductions areconsiderably simpler than the technically quite involved ones usedin earlier works on these problems. Using our constructions, we canfor the first time prove NP-hardness of these problems for all realdistance-power gradients α 0 (resp. α 1 forbroadcast) in 2D, and prove APX-hardness of all three problems in3D for all α 1. Our reductions yield improved lowerbounds on the approximation ratios for all problems whereAPX-hardness was known before already. In particular, we derive theoverall first APX-hardness proof for broadcast. This was an openproblem posed in earlier work in this area, as was the questionwhether (strong) connectivity remains NP-hard for α = 1. Inaddition, we give the first hardness results for so-calledwell-spread instances. On the positive side, we prove that twonatural greedy algorithms are 2-approximations for (strong)connectivity, and show that the factor 2 is tight inℝ2 for α 1. We also analyze theperformance guarantee of the well-known MST-heuristic as a functionof the input size. © 2008 Wiley Periodicals, Inc. NETWORKS,2008