Complexity of Positive Influence Domination on Partial Grids

Abstract

The Positive Influence Domination (PID) problem asks to find a minimum cardinality subset of influencers among the vertices of an undirected graph such that at least half the number of neighbors of each vertex are influencers. The problem’s underlying model can be used to determine an economical way of promoting (and keeping) good habits in society by interpreting vertices as individuals, neighbors as social contacts, and influencers as, for example, healthy eaters. We show that the problem is NP-hard even when restricted to planar subcubic graphs. The same result turns out to apply for the so-called double total domination problem, which exhibits a similar behavior on this graph class. We use this insight to derive NP-hardness of PID on the class of induced partial grids via a technique relying on orthogonal graph drawing. Finally, we derive bounds on the size of optimal solutions for arbitrarily dimensioned grids.