The behavior of two interacting populations "hosts" and "parasites" is investigated on Cayley trees and scale-free networks. In the former case analytical and numerical arguments elucidate a phase diagram for the susceptible-infected-susceptible model, whose most interesting feature is the absence of a tricritical point as a function of the two independent spreading parameters. For scale-free graphs, the parasite population can be described effectively by its dynamics in a host background. This is shown both by considering the appropriate dynamical equations and by numerical simulations on Barabási-Albert networks with the major implication that in the thermodynamic limit the critical parasite spreading parameter vanishes. Some implications and generalizations are discussed.