We address the problem of designing a network so that certain connectivity requirements are satisfied, at minimum cost of the edges used. The requirements are specified for each subset of vertices in terms of the number of edges with one endpoint in the set. We address a class of such problems, where the connectivity is Ε½ . required for sets of bounded size, p. We show that for fixed p pF2 , the problem is NP-complete, regardless of whether the requirement function is proper or not. For this class of bounded network design problems, we describe an Ε½ . Olog p -approximation algorithm for the case of a proper requirement function. We introduce a relaxation of the network design problem on directed graphs, where the requirement of each set is satisfied by the arcs that have their tails in the set. The relaxation allows arcs within the set to count toward the requirement of the set. We show that this relaxed problem is polynomial-time solvable if the requirement function is proper. The corresponding relaxation of the undirected problem is also polynomial-time solvable when the requirement function is proper. It is shown that in the case where the requirement function is not proper, the relaxed version is NP-complete. The integer relaxed problem or its linear programming relaxation is used to produce an approximate solution to the network design problem. Our analysis illustrates that the requirement of properness affects the difficulty of the problem.