HOME

TheInfoList



OR:

Set packing is a classical
NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...
problem in
computational complexity theory In theoretical computer science and mathematics, 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 ...
and
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
, and was one of
Karp's 21 NP-complete problems In computational complexity theory, Karp's 21 NP-complete problems are a set of computational problems which are NP-complete. In his 1972 paper, "Reducibility Among Combinatorial Problems", Richard Karp used Stephen Cook's 1971 theorem that the b ...
. Suppose one has a
finite set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. T ...
''S'' and a list of
subset In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
s 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 \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 computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whe ...
, 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, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables ...
, 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, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
. 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 or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objectiv ...
, belonging to the class of
packing problems Packing problems are a class of optimization problems in mathematics that involve attempting to pack objects together into containers. The goal is to either pack a single container as densely as possible or pack all objects using as few conta ...
.


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 or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objectiv ...
.


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 cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. It has several different formulations depending on which cli ...
; 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.


Packing sets with a bounded size

The problem does have a variant which is more tractable. Given any positive integer ''k''≥3, the ''k''-set packing problem is a variant of set packing in which each set contains at most ''k'' elements. When ''k''=1, the problem is trivial. When ''k''=2, the problem is equivalent to finding a
maximum cardinality matching Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adj ...
, which can be solved in polynomial time. For any ''k''≥3, the problem is NP-hard, as it is more general than
3-dimensional matching In the mathematical discipline of graph theory, a 3-dimensional matching is a generalization of bipartite matching (also known as 2-dimensional matching) to 3-partite hypergraphs, which consist of hyperedges each of which contains 3 vertices (in ...
. However, there are
constant-factor approximation algorithms In computational complexity theory, the class APX (an abbreviation of "approximable") is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant (or constant-factor ...
: * Cygan presented an algorithm that, for any ε>0, attains a (''k''+1+ε)/3 approximation. The run-time is polynomial in the number of sets and elements, but doubly-exponential in 1/ε. * Furer and Yu presented an algorithm that attains the same approximation, but with run-time singly-exponential in 1/ε.


Packing sets with a bounded degree

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 In graph theory, a matching in a hypergraph is a set of hyperedges, in which every two hyperedges are disjoint. It is an extension of the notion of matching in a graph. Definition Recall that a hypergraph is a pair , where is a set of ve ...
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 reductions between solutions to optimization problems. It preserves the property that a problem has a polynomial time appro ...
, and it shows that the two problems are equally difficult to approximate. In the special case when each set contains at most ''k'' elements (the ''k-set packing problem''), the intersection graph is (''k''+1)-
claw-free In the mathematical and computer science field of cryptography, a group of three numbers (''x'',''y'',''z'') is said to be a claw of two permutations ''f''0 and ''f''1 if :''f''0(''x'') = ''f''1(''y'') = ''z''. A pair of permutations ''f''0 and ...
. This is because, if a set intersects some ''k''+1 sets, then at least two of these sets intersect, so there cannot be a (''k''+1)-claw. So Maximum Independent Set in claw-free graphs can be seen as a generalization of Maximum ''k''-Set Packing.


Special cases

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 In the mathematical discipline of graph theory, a 3-dimensional matching is a generalization of bipartite matching (also known as 2-dimensional matching) to 3-partite hypergraphs, which consist of hyperedges each of which contains 3 vertices (in ...
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 The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972. Given a set of elements (called the un ...
, 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, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...
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, a singleton, also known as a unit set or one-point set, is a set with exactly one element. For example, the set \ is a singleton whose single element is 0. Properties Within the framework of Zermelo–Fraenkel set theory, the ...
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 In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. It has several different formulations depending on which cli ...
.


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, Exc ...
and
Gerhard Woeginger Gerhard J. Woeginger (31 May 1964 – 1 April 2022) was an Austrian mathematician and computer scientist who worked in Germany as a professor at RWTH Aachen University, where he chaired the algorithms and complexity group in the department of co ...
.
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