Establishing herd immunity is hard even in simple geometric networks (Q6057292)

The paper establishes that herd immunity is hard even in simple geometric networks. It studies the target set selection problem restricted to instances where the underlying graph is a unit disk graph. It is shown that target set selection problem is NP-complete on unit disk graphs even if the threshold function is bounded by a constant \(c\ge 2\), is equal to majority, or is unanimous. For grid graphs, it is shown that target set selection problem is NP-complete for constant and majority threshold and it is polynomial-time solvable for unanimous thresholds. Furthermore, the paper shows that the problem is solvable in polynomial-time on interval graphs even if the threshold function is unanimous. For the entire collection see [Zbl 1521.68009].