The Homogeneous Broadcast Problem in Narrow and Wide Strips II: Lower Bounds

• Published in: Algorithmica 2019-07, Vol.81 (7), p.2963-2990
• Main Authors: de Berg, Mark, Bodlaender, Hans L., Kisfaludi-Bak, Sándor
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Algorithms; Complexity; Computer Science; Computer Systems Organization and Communication Networks; Data Structures and Information Theory; Lower bounds; Mathematics of Computing; Nodes; Routing; Satellites; Theory of Computation; Wireless networks
• ISSN: 0178-4617; 1432-0541
• DOI: 10.1007/s00453-019-00561-0

Let P be a set of nodes in a wireless network, where each node is modeled as a point in the plane, and let s ∈ P be a given source node. Each node  p can transmit information to all other nodes within unit distance, provided  p is activated. The (homogeneous) broadcast problem is to activate a minimum number of nodes such that in the resulting directed communication graph, the source  s can reach any other node. We study the complexity of the regular and the hop-bounded version of the problem—in the latter s must be able to reach every node within a specified number of hops—where we also consider how the complexity depends on the width  w of the strip. We prove the following two lower bounds. First, we show that the regular version of the problem is W [ 1 ] -complete when parameterized by the solution size  k . More precisely, we show that the problem does not admit an algorithm with running time f ( k ) n o ( k ) , unless ETH fails. The construction can also be used to show an f ( w ) n Ω ( w ) lower bound when we parameterize by the strip width  w . 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).