A special case of the weighted set cover problem

A weighted set-cover problem contains a finite set 𝑆 and a collection Ω of its subsets. A nonnegative weight 𝑤_𝑗 is associated with each 𝑈_𝑗 ∈ Ω. The problem is to find a subcollection of ℧ with minimum weight so that the union of its sets is equal to 𝑆. This problem is a classic NP-hard combinatorial problem. In this paper, we investigate a special case of the problem that can be solved in strongly polynomial time where any two sets either have empty intersection or overlap completely. It is shown how this case may be transformed to a minimum cut problem. An example is given to illustrate the method.