We consider the problem of discovering overlapping communities in networks which we model as generalizations of the Set and Graph Packing problems with overlap. As usual for Set Packing problems we seek a collection \(\mathcal {S}' \subseteq \mathcal {S}\) consisting of at least \(k\) sets subject to certain disjointness restrictions. In the \(r\)-Set Packing with \(t\)-Membership, each element of \(\mathcal {U}\) belongs to at most \(t\) sets of \(\mathcal {S'}\) while in \(r\)-Set Packing with \(t\)-Overlap each pair of sets in \(\mathcal {S'}\) overlaps in at most \(t\) elements. For both problems, each set of \(\mathcal {S}\) has at most \(r\) elements.