  The least cost influence maximization problem aims to determine minimum cost
of partial (e.g., monetary) incentives initially given to the influential
spreaders on a social network, so that these early adopters exert influence
toward their neighbors and prompt influence propagation to reach a desired
penetration rate by the end of cascading processes. We first conduct polyhedral
analysis on a substructure that describes influence propagation assuming
influence weights are unequal, linear and additively separable. Two classes of
facet-defining inequalities based on a mixed 0-1 knapsack set contained in this
substructure are proposed. We characterize another exponential class of valid
and facet-defining inequalities utilizing the concept of minimum influencing
subset. We show that these inequalities can be separated in polynomial time
efficiently. Furthermore, a polynomial-time dynamic programming recursion is
presented to solve this problem on a simple cycle graph. For arbitrary graphs,
we propose a new exponential class of valid inequalities that dominates the
cycle elimination constraints and an efficient separation algorithm for them. A
compact convex hull description for a special case is presented. We illustrate
the effectiveness of these inequalities via a delayed cut generation algorithm
in the computational experiments.
