HOME

TheInfoList




Set packing is a classical
NP-complete In computational complexity theory Computational complexity theory focuses on classifying computational problem In theoretical computer science An artistic representation of a Turing machine. Turing machines are used to model general computi ...
problem in
computational complexity theory Computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by ...
and
combinatorics Combinatorics is an area of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geom ...
, and was one of
Karp's 21 NP-complete problemsIn computational complexity theory Computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A ...
. Suppose one has a
finite set In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...
''S'' and a list of
subset In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...

subset
s of ''S''. Then, the set packing problem asks if some ''k'' subsets in the list are pairwise
disjoint
disjoint
(in other words, no two of them share an element). More formally, given a universe \mathcal and a family \mathcal of subsets of \mathcal, a ''packing'' is a subfamily \mathcal\subseteq\mathcal of sets such that all sets in \mathcal are pairwise disjoint. The size of the packing is , \mathcal, . In the set packing
decision problem In computability theory and computational complexity theory, a decision problem is a problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding whether a given natural number is prime. Anot ...
, the input is a pair (\mathcal,\mathcal) and an integer k; the question is whether there is a set packing of size k or more. In the set packing
optimization problem In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...
, the input is a pair (\mathcal,\mathcal), 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 In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of com ...
. 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 An integer programming problem is a mathematical optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of ...
, belonging to the class of
packing problems Packing problems are a class of optimization problem In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), a ...
.


Integer linear program formulation

The maximum set packing problem can be formulated as the following
integer linear program An integer programming problem is a mathematical optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of ...
.


Complexity

The set packing problem is not only NP-complete, but its optimization version (general maximum set packing problem) has been proven as difficult to approximate as the
maximum clique problem In computer science, the clique problem is the computational problem of finding clique (graph theory), cliques (subsets of vertices, all Adjacent (graph theory), adjacent to each other, also called complete graph, complete Glossary of graph theo ...
; in particular, it cannot be approximated within any constant factor. The best known algorithm approximates it within a factor of O(\sqrt). The weighted variant can also be approximated as well. However, the problem does have a variant which is more tractable: if we assume no subset exceeds ''k''≥3 elements, the answer can be approximated within a factor of ''k''/2 + ε for any ε > 0; in particular, the problem with 3-element sets can be approximated within about 50%. In another more tractable variant, if no element occurs in more than ''k'' of the subsets, the answer can be approximated within a factor of ''k''. This is also true for the weighted version.


Related problems


Equivalent problems

Hypergraph matching is equivalent to set packing: the sets correspond to the hyperedges. The independent set problem is also equivalent to set packing - there is a one-to-one polynomial-time reduction between them: * Given a set packing problem on a collection \mathcal, build a graph where for each set S \in \mathcal there is a vertex v_S, and there is an edge between v_S and v_T iff S \cap T \neq \varnothing. Every independent set of vertices in the generated graph corresponds to a set packing in \mathcal. * Given an independent vertex set problem on a graph G(V,E), build a collection of sets where for each vertex v there is a set S_v containing all edges adjacent to v. Every set packing in the generated collection corresponds to an independent vertex set in G(V,E). This is also a bidirectional
PTAS reduction In computational complexity theory, a PTAS reduction is an approximation-preserving reduction that is often used to perform Reduction (complexity), reductions between solutions to optimization problems. It preserves the property that a problem has a ...
, and it shows that the two problems are equally difficult to approximate.


Special cases

Graph matching
Graph matching
is a special case of set packing in which the size of all sets is 2 (the sets correspond to the edges). In this special case, a maximum-size matching can be found in polynomial time. 3-dimensional matching is a special case in which the size of all sets is 3, and in addition, the elements are partitioned into 3 colors and each set contains exactly one element of each color. This special case is still NP-hard, though it has better constant-factor approximation algorithms than the general case.


Other related problems

In the set cover problem, we are given a family \mathcal of subsets of a universe \mathcal, and the goal is to determine whether we can choose ''k'' sets that together contain every element of \mathcal. These sets may overlap. The optimization version finds the minimum number of such sets. The maximum set packing need not cover every possible element. In the exact cover problem, every element of \mathcal should be contained in ''exactly one'' of the subsets. Finding such an exact cover is an
NP-complete In computational complexity theory Computational complexity theory focuses on classifying computational problem In theoretical computer science An artistic representation of a Turing machine. Turing machines are used to model general computi ...
problem, even in the special case in which the size of all sets is 3 (this special case is called exact 3 cover or X3C). However, if we create a
singleton set In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
for each element of ''S'' and add these to the list, the resulting problem is about as easy as set packing. Karp originally showed set packing NP-complete via a reduction from the clique problem. See also: Packing in a hypergraph.


Notes


References


Maximum Set Packing
Viggo Kann. *

. ''Dictionary of Algorithms and Data Structures'', editor Paul E. Black, ''National Institute of Standards and Technology.'' Note that the definition here is somewhat different. * Steven S. Skiena.
Set Packing
. ''The Algorithm Design Manual''. * Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson,
Marek Karpinski Marek KarpinskiMarek Karpinski Biography
at the Hausdorff Center for Mathematics, Excel ...

Marek Karpinski
and Gerhard Woeginger.
Maximum Set Packing

''A compendium of NP optimization problems''
Last modified March 20, 2000. * A3.1: SP3, pg.221. *


External links



A Pascal program for solving the problem. From ''Discrete Optimization Algorithms with Pascal Programs'' by MacIej M. Syslo, .
Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Winner DeterminationOptimizing Three-Dimensional Bin Packing
{{Packing problem Combinatorics NP-complete problems