This paper proposes an algorithm to compute marginal reliability importance for network systems with k-terminal reliability efficiently. Marginal reliability importance is an appropriate quantitative measure on a system component against system reliability and it contributes to design of reliable systems. Computing marginal reliability importance in network systems is time-consuming due to its NP-hardness. This paper extends the algorithm proposed in our last study to deal with k-terminal reliability and incorporates an extended factoring theorem to improve the algorithm. Numerical experiments compare the proposed algorithm with a traditional method to reveal efficiency of the algorithm. The algorithm helps to construct efficient algorithm to reliable network design problems. © World Scientific Publishing Company.