Given a digraph (or an undirected graph) G = (V,E) with a set V of vertices v with nonnegative real costs w(v), and a set E of edges and a positive integer k, we deal with the problem of finding a minimum cost subset S ⊆ V such that, for each vertex v ∈ V-S, there are k vertex-disjoint paths from S to v. In this paper, we show that the problem can be solved by a greedy algorithm in O(min{k, √n}nm) time in a digraph (or in O(min{k, √n}kn2) time in an undirected graph), where n = |V| and m = |E|. Based on this, given a digraph and two integers k and ℓ, we also give a polynomial time algorithm for finding a minimum cost subset S ⊆ V such that for each vertex v ∈ V-S, there are k vertex-disjoint paths from S to v as well as ℓ vertex-disjoint paths from v to S. © 2001 Elsevier Science B.V. All rights reserved.