Sending Messages in Social Networks

Since the birth of digital social networks, management research focused upon the opportunities of social media marketing. A marketing campaign has the best success when it reaches the largest number of potential customers. It is, however, difficult to forecast in a precise way the number of contacts that you can reach with such an initiative. We propose a representation of social networks that captures both the probability of forecasting a message to different agents, and the time span during which the message is sent out. We study reachiability and coverage from the computational complexity viewpoint and show that they can be solved polynomially on deterministic machines.