Set cover problem

Last updated November 17, 2024

The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory.

Given a set of elements ${1, 2, \dots, n}$ (henceforth referred to as the universe, specifying all possible elements under consideration) and a collection, referred to as $S$ , of a given $m$ subsets whose union equals the universe, the set cover problem is to identify a smallest sub-collection of $S$ whose union equals the universe.

For example, consider the universe, $U = {1, 2, 3, 4, 5}$ and the collection of sets $S = { {1, 2, 3}, {2, 4}, {3, 4}, {4, 5} }.$ In this example, $m$ is equal to 4, as there are four subsets that comprise this collection. The union of $S$ is equal to $U$ . However, we can cover all elements with only two sets: ${ {1, 2, 3}, {4, 5} }‍$ , see picture, but not with only one set. Therefore, the solution to the set cover problem for this $U$ and $S$ has size 2.

More formally, given a universe ${\mathcal {U}}$ and a family ${\mathcal {S}}$ of subsets of ${\mathcal {U}}$ , a set cover is a subfamily ${\mathcal {C}}\subseteq {\mathcal {S}}$ of sets whose union is ${\mathcal {U}}$ .

In the set cover decision problem, the input is a pair $({\mathcal {U}},{\mathcal {S}})$ and an integer $k$ ; the question is whether there is a set cover of size $k$ or less.
In the set cover optimization problem, the input is a pair $({\mathcal {U}},{\mathcal {S}})$ , and the task is to find a set cover that uses the fewest sets.

The decision version of set covering is NP-complete. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972. The optimization/search version of set cover is NP-hard.^[1] It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms.^[2]

Variants

In the weighted set cover problem, each set is assigned a positive weight (representing its cost), and the goal is to find a set cover with a smallest weight. The usual (unweighted) set cover corresponds to all sets having a weight of 1.

In the fractional set cover problem, it is allowed to select fractions of sets, rather than entire sets. A fractional set cover is an assignment of a fraction (a number in [0,1]) to each set in ${\mathcal {S}}$ , such that for each element x in the universe, the sum of fractions of sets that contain x is at least 1. The goal is to find a fractional set cover in which the sum of fractions is as small as possible. Note that a (usual) set cover is equivalent to a fractional set cover in which all fractions are either 0 or 1; therefore, the size of the smallest fractional cover is at most the size of the smallest cover, but may be smaller. For example, consider the universe $U = {1, 2, 3}$ and the collection of sets $S = { {1, 2}, {2, 3}, {3, 1} }.$ The smallest set cover has a size of 2, e.g. ${ {1, 2}, {2, 3} }.$ But there is a fractional set cover of size 1.5, in which a 0.5 fraction of each set is taken.

Linear program formulation

The set cover problem can be formulated as the following integer linear program (ILP).^[3]

minimize	$\sum _{s\in {\mathcal {S}}}x_{s}$		(minimize the number of sets)
subject to	$\sum _{s\colon e\in s}x_{s}\geqslant 1$	for all $e\in {\mathcal {U}}$	(cover every element of the universe)
	$x_{s}\in \{0,1\}$	for all $s\in {\mathcal {S}}$ .	(every set is either in the set cover or not)

For a more compact representation of the covering constraint, one can define an incidence matrix $A$ , where each row corresponds to an element and each column corresponds to a set, and $A_{e,s}=1$ if element e is in set s, and $A_{e,s}=0$ otherwise. Then, the covering constraint can be written as $Ax\geqslant 1$ .

Weighted set cover is described by a program identical to the one given above, except that the objective function to minimize is $\sum _{s\in {\mathcal {S}}}w_{s}x_{s}$ , where $w_{s}$ is the weight of set $s\in {\mathcal {S}}$ .

Fractional set cover is described by a program identical to the one given above, except that $x_{s}$ can be non-integer, so the last constraint is replaced by $0\leq x_{s}\leq 1$ .

This linear program belongs to the more general class of LPs for covering problems, as all the coefficients in the objective function and both sides of the constraints are non-negative. The integrality gap of the ILP is at most $\scriptstyle \log n$ (where $\scriptstyle n$ is the size of the universe). It has been shown that its relaxation indeed gives a factor- $\scriptstyle \log n$ approximation algorithm for the minimum set cover problem.^[4] See randomized rounding#setcover for a detailed explanation.

Hitting set formulation

Set covering is equivalent to the hitting set problem. That is seen by observing that an instance of set covering can be viewed as an arbitrary bipartite graph, with the universe represented by vertices on the left, the sets represented by vertices on the right, and edges representing the membership of elements to sets. The task is then to find a minimum cardinality subset of left-vertices that has a non-trivial intersection with each of the right-vertices, which is precisely the hitting set problem.

In the field of computational geometry, a hitting set for a collection of geometrical objects is also called a stabbing set or piercing set.^[5]

Greedy algorithm

There is a greedy algorithm for polynomial time approximation of set covering that chooses sets according to one rule: at each stage, choose the set that contains the largest number of uncovered elements. This method can be implemented in time linear in the sum of sizes of the input sets, using a bucket queue to prioritize the sets.^[6] It achieves an approximation ratio of $H(s)$ , where $s$ is the size of the set to be covered.^[7] In other words, it finds a covering that may be $H(n)$ times as large as the minimum one, where $H(n)$ is the $n$ -th harmonic number: $H(n)=\sum _{k=1}^{n}{\frac {1}{k}}\leq \ln {n}+1$

This greedy algorithm actually achieves an approximation ratio of $H(s^{\prime })$ where $s^{\prime }$ is the maximum cardinality set of $S$ . For $\delta -$ dense instances, however, there exists a $c\ln {m}$ -approximation algorithm for every $c>0$ .^[8]

Tight example for the greedy algorithm with k=3 SetCoverGreedy.gif — Tight example for the greedy algorithm with k=3

There is a standard example on which the greedy algorithm achieves an approximation ratio of $\log _{2}(n)/2$ . The universe consists of $n=2^{(k+1)}-2$ elements. The set system consists of $k$ pairwise disjoint sets $S_{1},\ldots ,S_{k}$ with sizes $2,4,8,\ldots ,2^{k}$ respectively, as well as two additional disjoint sets $T_{0},T_{1}$ , each of which contains half of the elements from each $S_{i}$ . On this input, the greedy algorithm takes the sets $S_{k},\ldots ,S_{1}$ , in that order, while the optimal solution consists only of $T_{0}$ and $T_{1}$ . An example of such an input for $k=3$ is pictured on the right.

Inapproximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation algorithm for set cover up to lower order terms (see Inapproximability results below), under plausible complexity assumptions. A tighter analysis for the greedy algorithm shows that the approximation ratio is exactly $\ln {n}-\ln {\ln {n}}+\Theta (1)$ .^[9]

Low-frequency systems

If each element occurs in at most f sets, then a solution can be found in polynomial time that approximates the optimum to within a factor of f using LP relaxation.

If the constraint $x_{S}\in \{0,1\}$ is replaced by $x_{S}\geq 0$ for all S in ${\mathcal {S}}$ in the integer linear program shown above, then it becomes a (non-integer) linear program L. The algorithm can be described as follows:

Find an optimal solution O for the program L using some polynomial-time method of solving linear programs.
Pick all sets S for which the corresponding variable x_S has value at least 1/f in the solution O.^[10]

Inapproximability results

When $n$ refers to the size of the universe, Lund & Yannakakis (1994) showed that set covering cannot be approximated in polynomial time to within a factor of ${\tfrac {1}{2}}\log _{2}{n}\approx 0.72\ln {n}$ , unless NP has quasi-polynomial time algorithms. Feige (1998) improved this lower bound to ${\bigl (}1-o(1){\bigr )}\cdot \ln {n}$ under the same assumptions, which essentially matches the approximation ratio achieved by the greedy algorithm. Raz & Safra (1997) established a lower bound of $c\cdot \ln {n}$ , where $c$ is a certain constant, under the weaker assumption that P $\not =$ NP. A similar result with a higher value of $c$ was recently proved by Alon, Moshkovitz & Safra (2006). Dinur & Steurer (2013) showed optimal inapproximability by proving that it cannot be approximated to ${\bigl (}1-o(1){\bigr )}\cdot \ln {n}$ unless P $=$ NP.

In low-frequency systems, Dinur et al. (2003) proved it is NP-hard to approximate set cover to better than $f-1-\epsilon$ . If the Unique games conjecture is true, this can be improved to $f-\epsilon$ as proven by Khot & Regev (2008).

Trevisan (2001) proves that set cover instances with sets of size at most $\Delta$ cannot be approximated to a factor better than $\ln \Delta -O(\ln \ln \Delta )$ unless P $=$ NP, thus making the approximation of $\ln \Delta +1$ of the greedy algorithm essentially tight in this case.

Weighted set cover

Relaxing the integer linear program for weighted set cover stated above, one may use randomized rounding to get an $O(\log n)$ -factor approximation. Non weighted set cover can be adapted to the weighted case.^[11]

Fractional set cover

Notes

↑ Korte & Vygen 2012, p. 414.
↑ Vazirani (2001 , p. 15)
↑ Vazirani (2001 , p. 108)
↑ Vazirani (2001 , pp. 110–112)
↑ Nielsen, Frank (2000-09-06). "Fast stabbing of boxes in high dimensions" (PDF). Theoretical Computer Science. 246 (1): 53–72. doi: 10.1016/S0304-3975(98)00336-3 . ISSN 0304-3975.
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990], "Exercise 35.3-3", Introduction to Algorithms (3rd ed.), MIT Press and McGraw-Hill, p. 1122, ISBN 0-262-03384-4
↑ Chvatal, V. (August 1979), "A Greedy Heuristic for the Set-Covering Problem", Mathematics of Operations Research , 4 (3): 233–235, doi:10.1287/moor.4.3.233, JSTOR 3689577
↑ Karpinski & Zelikovsky 1998
↑ Slavík Petr A tight analysis of the greedy algorithm for set cover. STOC'96, Pages 435-441, doi : 10.1145/237814.237991
↑ Vazirani (2001 , pp. 118–119)
↑ Vazirani (2001 , Chapter 14)
↑ Information., Sandia National Laboratories. United States. Department of Energy. United States. Department of Energy. Office of Scientific and Technical (1999). On the Red-Blue Set Cover Problem. United States. Dept. of Energy. OCLC 68396743.
↑ Gainer-Dewar, Andrew; Vera-Licona, Paola (2017), "The minimal hitting set generation problem: algorithms and computation", SIAM Journal on Discrete Mathematics , 31 (1): 63–100, arXiv: 1601.02939 , doi:10.1137/15M1055024, MR 3590650, S2CID 9240467

Related Research Articles

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

In combinatorial mathematics, the Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a number of settings, they all require an optimal interconnect for a given set of objects and a predefined objective function. One well-known variant, which is often used synonymously with the term Steiner tree problem, is the Steiner tree problem in graphs. Given an undirected graph with non-negative edge weights and a subset of vertices, usually referred to as terminals, the Steiner tree problem in graphs requires a tree of minimum weight that contains all terminals and minimizes the total weight of its edges. Further well-known variants are the Euclidean Steiner tree problem and the rectilinear minimum Steiner tree problem.

In graph theory, a vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time. The field of approximation algorithms, therefore, tries to understand how closely it is possible to approximate optimal solutions to such problems in polynomial time. In an overwhelming majority of the cases, the guarantee of such algorithms is a multiplicative one expressed as an approximation ratio or approximation factor i.e., the optimal solution is always guaranteed to be within a (predetermined) multiplicative factor of the returned solution. However, there are also many approximation algorithms that provide an additive guarantee on the quality of the returned solution. A notable example of an approximation algorithm that provides both is the classic approximation algorithm of Lenstra, Shmoys and Tardos for scheduling on unrelated parallel machines.

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. Finding a matching in a bipartite graph can be treated as a network flow problem.

<span class="mw-page-title-main">Dominating set</span> Subset of a graphs nodes such that all other nodes link to at least one

In graph theory, a dominating set for a graph $G$ is a subset $D$ of its vertices, such that any vertex of $G$ is in $D$ , or has a neighbor in $D$ . The domination number $γ(G)$ is the number of vertices in a smallest dominating set for $G$ .

In graph theory, a domatic partition of a graph $is a partition of into disjoint sets,,..., such that each V i is a dominating set for G . The figure on the right shows a domatic partition of a graph; here the dominating set consists of the yellow vertices, consists of the green vertices, and consists of the blue vertices.$

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 graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connected graph, each cut-set determines a unique cut, and in some cases cuts are identified with their cut-sets rather than with their vertex partitions.

In computer science, the shortest common supersequence of two sequences X and Y is the shortest sequence which has X and Y as subsequences. This is a problem closely related to the longest common subsequence problem. Given two sequences X = < x₁,...,x_m > and Y = < y₁,...,y_n >, a sequence U = < u₁,...,u_k > is a common supersequence of X and Y if items can be removed from U to produce X and Y.

In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable.

In the mathematical fields of graph theory and combinatorial optimization, the bipartite dimension or biclique cover number of a graph G = (V, E) is the minimum number of bicliques (that is complete bipartite subgraphs), needed to cover all edges in E. A collection of bicliques covering all edges in G is called a biclique edge cover, or sometimes biclique cover. The bipartite dimension of G is often denoted by the symbol d(G).

The maximum coverage problem is a classical question in computer science, computational complexity theory, and operations research. It is a problem that is widely taught in approximation algorithms.

In graph theory, the metric $k$ -center problem or vertex k-center problem is a classical combinatorial optimization problem studied in theoretical computer science that is NP-hard. Given $n$ cities with specified distances, one wants to build $k$ warehouses in different cities and minimize the maximum distance of a city to a warehouse. In graph theory, this means finding a set of $k$ vertices for which the largest distance of any point to its closest vertex in the $k$ -set is minimum. The vertices must be in a metric space, providing a complete graph that satisfies the triangle inequality. It has application in facility location and clustering.

In computer science and operations research, randomized rounding is a widely used approach for designing and analyzing approximation algorithms.

In theoretical computer science, the term isolation lemma refers to randomized algorithms that reduce the number of solutions to a problem to one, should a solution exist. This is achieved by constructing random constraints such that, with non-negligible probability, exactly one solution satisfies these additional constraints if the solution space is not empty. Isolation lemmas have important applications in computer science, such as the Valiant–Vazirani theorem and Toda's theorem in computational complexity theory.

In the mathematical field of graph theory, the intersection number of a graph $is the smallest number of elements in a representation of as an intersection graph of finite sets. In such a representation, each vertex is represented as a set, and two vertices are connected by an edge whenever their sets have a common element. Equivalently, the intersection number is the smallest number of cliques needed to cover all of the edges of .$

In graph theory and computer science, a dense subgraph is a subgraph with many edges per vertex. This is formalized as follows: let $G = (V, E)$ be an undirected graph and let $S = (V S, E S)$ be a subgraph of $G$ . Then the density of $S$ is defined to be:

The geometric set cover problem is the special case of the set cover problem in geometric settings. The input is a range space $where is a universe of points in and is a family of subsets of called ranges, defined by the intersection of and geometric shapes such as disks and axis-parallel rectangles. The goal is to select a minimum-size subset of ranges such that every point in the universe is covered by some range in .$

The welfare maximization problem is an optimization problem studied in economics and computer science. Its goal is to partition a set of items among agents with different utility functions, such that the welfare – defined as the sum of the agents' utilities – is as high as possible. In other words, the goal is to find an item allocation satisfying the utilitarian rule.

References

Alon, Noga; Moshkovitz, Dana; Safra, Shmuel (2006), "Algorithmic construction of sets for k-restrictions", ACM Trans. Algorithms, 2 (2): 153–177, CiteSeerX 10.1.1.138.8682 , doi:10.1145/1150334.1150336, ISSN 1549-6325, S2CID 11922650 .
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms, Cambridge, Mass.: MIT Press and McGraw-Hill, pp. 1033–1038, ISBN 978-0-262-03293-3
Feige, Uriel (1998), "A threshold of ln n for approximating set cover", Journal of the ACM , 45 (4): 634–652, CiteSeerX 10.1.1.70.5014 , doi:10.1145/285055.285059, ISSN 0004-5411, S2CID 52827488 .
Karpinski, Marek; Zelikovsky, Alexander (1998), "Approximating dense cases of covering problems", Proceedings of the DIMACS Workshop on Network Design: Connectivity and Facilities Location, vol. 40, American Mathematical Society, pp. 169–178, ISBN 9780821870846
Lund, Carsten; Yannakakis, Mihalis (1994), "On the hardness of approximating minimization problems", Journal of the ACM , 41 (5): 960–981, doi: 10.1145/185675.306789 , ISSN 0004-5411, S2CID 9021065 .
Raz, Ran; Safra, Shmuel (1997), "A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP", STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, ACM, pp. 475–484, ISBN 978-0-89791-888-6 .
Dinur, Irit; Steurer, David (2013), "Analytical approach to parallel repetition", STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing, ACM, pp. 624–633.
Vazirani, Vijay V. (2001), Approximation Algorithms (PDF), Springer-Verlag, ISBN 978-3-540-65367-7
Korte, Bernhard; Vygen, Jens (2012), Combinatorial Optimization: Theory and Algorithms (5 ed.), Springer, ISBN 978-3-642-24487-2
Cardoso, Nuno; Abreu, Rui (2014), "An Efficient Distributed Algorithm for Computing Minimal Hitting Sets" (PDF), Proceedings of the 25th International Workshop on Principles of Diagnosis, Graz, Austria, doi:10.5281/zenodo.10037 {{citation}}: CS1 maint: location missing publisher (link)
Dinur, Irit; Guruswami, Venkatesan; Khot, Subhash; Regev, Oded (2003), A new multilayered PCP and the hardness of hypergraph vertex cover, Association for Computing Machinery, pp. 595–601, doi:10.1145/780542.780629, ISBN 1581136749
Khot, Subhash; Regev, Oded (2008), Vertex cover might be hard to approximate to within 2− $\epsilon$ , Journal of Computer and System Sciences, pp. 335–349, doi:10.1016/j.jcss.2007.06.019
Trevisan, Luca (2001), "Non-approximability results for optimization problems on bounded degree instances", Proceedings of the thirty-third annual ACM symposium on Theory of computing, Association for Computing Machinery, pp. 453–461, doi:10.1145/380752.380839, ISBN 1-58113-349-9

External links

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[FOOTNOTEKorteVygen2012414-1] Korte & Vygen 2012, p. 414.

[2] Vazirani (2001 , p. 15)

[3] Vazirani (2001 , p. 108)

[4] Vazirani (2001 , pp. 110–112)

[5] Nielsen, Frank (2000-09-06). "Fast stabbing of boxes in high dimensions" (PDF). Theoretical Computer Science. 246 (1): 53–72. doi: 10.1016/S0304-3975(98)00336-3 . ISSN 0304-3975.

[6] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990], "Exercise 35.3-3", Introduction to Algorithms (3rd ed.), MIT Press and McGraw-Hill, p. 1122, ISBN 0-262-03384-4

[7] Chvatal, V. (August 1979), "A Greedy Heuristic for the Set-Covering Problem", Mathematics of Operations Research , 4 (3): 233–235, doi:10.1287/moor.4.3.233, JSTOR 3689577

[8] Karpinski & Zelikovsky 1998

[9] Slavík Petr A tight analysis of the greedy algorithm for set cover. STOC'96, Pages 435-441, doi : 10.1145/237814.237991

[10] Vazirani (2001 , pp. 118–119)

[11] Vazirani (2001 , Chapter 14)

[12] Information., Sandia National Laboratories. United States. Department of Energy. United States. Department of Energy. Office of Scientific and Technical (1999). On the Red-Blue Set Cover Problem. United States. Dept. of Energy. OCLC 68396743.

[13] Gainer-Dewar, Andrew; Vera-Licona, Paola (2017), "The minimal hitting set generation problem: algorithms and computation", SIAM Journal on Discrete Mathematics , 31 (1): 63–100, arXiv: 1601.02939 , doi:10.1137/15M1055024, MR 3590650, S2CID 9240467

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]