Set packing

Set packing is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NP-complete problems. Set packing is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NP-complete problems. Suppose one has a finite set S and a list of subsets of S. Then, the set packing problem asks if some k subsets in the list are pairwise disjoint (in other words, no two of them share an element). More formally, given a universe U {displaystyle {mathcal {U}}} and a family S {displaystyle {mathcal {S}}} of subsets of U {displaystyle {mathcal {U}}} ,a packing is a subfamily C ⊆ S {displaystyle {mathcal {C}}subseteq {mathcal {S}}} of sets such that all sets in C {displaystyle {mathcal {C}}} are pairwise disjoint. The size of the packing is | C | {displaystyle |{mathcal {C}}|} . In the set packing decision problem, the input is a pair ( U , S ) {displaystyle ({mathcal {U}},{mathcal {S}})} and an integer k {displaystyle k} ; the question is whetherthere is a set packing of size k {displaystyle k} or more. In the set packing optimization problem, the input is a pair ( U , S ) {displaystyle ({mathcal {U}},{mathcal {S}})} , and the task is to find a set packing that uses the most sets. The problem is clearly in NP since, given k subsets, we can easily verify that they are pairwise disjoint in polynomial time. The optimization version of the problem, maximum set packing, asks for the maximum number of pairwise disjoint sets in the list. It is a maximization problem that can be formulated naturally as an integer linear program, belonging to the class of packing problems. The maximum set packing problem can be formulated as the following integer linear program. As a simple example, suppose your kitchen contains a collection of different food ingredients ( U {displaystyle {mathcal {U}}} ), and you have a cook-book with a collection of recipes ( S {displaystyle {mathcal {S}}} ). Each recipe requires a subset of the food ingredients. You want to prepare the largest possible collection of recipes from the cook-book. You are actually looking for a set-packing ( C {displaystyle {mathcal {C}}} ) on ( U , S {displaystyle {mathcal {U}},{mathcal {S}}} ) - a collection of recipes whose sets of ingredients are pairwise disjoint.