TOPICS
Search

Set Cover Problem

A set cover of a finite set U by a collection C of its subsets is a subcollection S subset= C such that

union _(S in S)S=U.

The set cover problem, also called the minimum cover problem, asks whether there is a set cover with at most k members. Its optimization version asks for a set cover of minimum cardinality.

The decision problem is NP-complete (Karp 1972). Set cover is dual to the hitting set problem, and the vertex cover problem is a related graph-theoretic special case.

See also

Hitting Set, Set Covering Deployment, Vertex Cover

Explore with Wolfram|Alpha

References

Karp, R. M. "Reducibility Among Combinatorial Problems." In Complexity of Computer Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972 (Ed. R. E. Miller and J. W. Thatcher). New York: Plenum, pp. 85-103, 1972. https://doi.org/10.1007/978-1-4684-2001-2_9.

Cite this as:

Weisstein, Eric W. "Set Cover Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SetCoverProblem.html

Subject classifications