TOPICS
Search

Set Cover Problem

The set cover problem, also called the minimum cover problem, asks whether a finite set U has a set cover with at most k members from a given collection C of its subsets. Such a set cover is a subcollection S subset= C satisfying

union _(S in S)S=U.

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