Being an Influencer is Hard: The Complexity of Influence Maximization in Temporal Graphs with a Fixed Source

We consider the influence maximization problem over a temporal graph, where there is a single fixed source. We deviate from the standard model of influence maximization, where the goal is to choose the set of most influential vertices. Instead, in our model we are given a fixed vertex, or source, and the goal is to find the best time steps to transmit so that the influence of this vertex is maximized. We frame this problem as a spreading process that follows a variant of susceptible-infected-susceptible (SIS) model and we focus on two objective functions. In the MaxSpread objective, the goal is to maximize the total number of vertices that get infected at least once. In the MaxViral objective, the goal is to maximize the number of vertices that are infected at the same time step. We perform a thorough complexity theoretic analysis for these two objectives over three different scenarios: (1) the unconstrained setting where the source can transmit whenever it wants; (2) the window-constrained setting where the source has to transmit at either a predetermined, or a shifting window; (3) the periodic setting where the temporal graph is periodic with a small period. We prove that, with the exception of MaxSpread for periodic graphs, all remaining problems are intractable even for very simple underlying graphs.