Abstract
A simple variant of the node connectivity problem arises in the domain of network reliability. Here, break-up of a network into two components can be tolerated, but not into three or more components. We show that the problem of determining the minimum number of node/edge deletions that break a network into three or more components is a computationally hard problem, by proving that its decision-version is NP-Complete. In the process, we show that a closely related problem, which can be of interest in itself, is also NP-Complete.