ALBERT

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉Let 〈em〉P〈/em〉 be a set of nodes in a wireless network, where each node is modeled as a point in the plane, and let 〈span〉 〈span〉\(s\in P\)〈/span〉 〈/span〉 be a given source node. Each node 〈em〉p〈/em〉 can transmit information to all other nodes within unit distance, provided 〈em〉p〈/em〉 is activated. The (homogeneous) broadcast problem is to activate a minimum number of nodes such that in the resulting directed communication graph, the source 〈em〉s〈/em〉 can reach any other node. We study the complexity of the regular and the hop-bounded version of the problem—in the latter 〈em〉s〈/em〉 must be able to reach every node within a specified number of hops—where we also consider how the complexity depends on the width 〈em〉w〈/em〉 of the strip. We prove the following two lower bounds. First, we show that the regular version of the problem is 〈span〉 〈span〉\({\mathsf {W[1]}}\)〈/span〉 〈/span〉-complete when parameterized by the solution size 〈em〉k〈/em〉. More precisely, we show that the problem does not admit an algorithm with running time 〈span〉 〈span〉\(f(k)n^{o(\sqrt{k})}\)〈/span〉 〈/span〉, unless ETH fails. The construction can also be used to show an 〈span〉 〈span〉\(f(w)n^{\varOmega (w)}\)〈/span〉 〈/span〉 lower bound when we parameterize by the strip width 〈em〉w〈/em〉. Second, we prove that the hop-bounded version of the problem is NP-hard in strips of width 40. These results complement the algorithmic results in a companion paper (de Berg et al. in Algorithmica, submitted).〈/p〉