We propose a cut-based formulation for the problem, and design two exact algorithmic approaches: one based on the separation of connectivity cut inequalities, and the other corresponding to a Benders decomposition of the former model. Both approaches are enhanced by various techniques, including (i) preprocessing, (ii) stabilized cut generation, (iii) primal heuristics, and (iv) cut management. These two algorithmic alternatives are computationally evaluated and compared with a previously proposed flow based formulation. We illustrate the effectiveness of the algorithms on two types of instances derived from protein-protein interaction networks (available from the previous literature) and from telecommunication access networks. (C) 2016 Elsevier B.V. All rights reserved.