Probabilistic connectivity problems arise naturally in many social networks.

In particular the spread of an epidemic across a population and social trust inference

motivate much of our work. We examine problems where some property, such as an

infection or influence, starts from some initially seeded set of nodes and every affected node transmits the property to its neighbors with a probability determined by

the connecting edge. Many problems in this area involve connectivity in a random-

graph - the probability of a node being affected is the probability that there is a

path to it in the random-graph from one of the seed nodes. We may wish to aid,

disrupt, or simply monitor this connectivity. In our core applications, public health

officials wish to minimize an epidemic's spread over a population, and connectivity in a social network suggests how closely tied its users are. In support of these

and other applications, we study several combinatorial optimization problems on

random-graphs. We derive algorithms and demonstrate their effectiveness through

simulation, mathematical proof, or both.