Can a requirement be covered more than once?

Yes. The standard constraint is at least once.

Does NP-hard mean no useful solution can be found?

No. Particular instances may be solved exactly, and approximation or heuristic methods can provide practical covers. The hardness claim concerns the general problem.

How does this relate to AI planning?

A relaxation can treat goal facts as elements and action effects as covering sets. Ignoring preconditions or destructive effects simplifies the task but may remove important planning interactions.

AI Glossary / Graphs and symbolic AI / Intermediate

Set-cover problem

Definition

The set-cover problem asks for a collection of available subsets whose union contains every required element, while minimizing the number of chosen subsets or their total cost. It models situations where one choice can satisfy several requirements and different choices overlap in what they cover.

What it means

The required elements form a universe. Available options are represented by subsets of that universe. A valid cover must include every required element at least once; covering an element more than once is allowed.

In the unweighted version, each selected subset counts equally. In weighted set cover, each has a specified cost, and the objective is to minimize the sum of selected costs. These are different objectives: the fewest options need not be the cheapest collection.

This is not the same as exact cover, which requires each element to be covered exactly once, or maximum coverage, which usually seeks as much coverage as possible within a budget. Those distinctions matter when converting a business request into an optimization model.

How it works

A model first records which option covers which requirement. It checks feasibility: if some required element belongs to no available subset, a complete cover is impossible under the current options.

An exact optimization formulation uses one yes/no variable per option. For each required element, the sum of variables for options containing it must be at least one. The objective minimizes selected count or total cost. The general optimization problem is NP-hard; its corresponding bounded-size decision version is NP-complete.

A common unweighted greedy method repeatedly selects the subset covering the most currently uncovered elements. A weighted variant considers cost per newly covered element. Such methods offer useful approximation guarantees under their standard assumptions, but they need not find the optimum. Coverage must be recalculated after each choice: a set's original size can overstate what it still contributes.

Three practical examples

A software team selects regression tests so that every listed feature is exercised by at least one chosen test, while recognizing that feature coverage does not prove defect detection.
A training coordinator chooses sessions whose combined topics include every required topic.
A facilities analyst compares candidate observation locations, each covering a defined group of areas, subject to the limits of the assumed coverage model.

Think of it this way

Think of choosing transparent sheets with different marked regions so that, together, the sheets cover every required spot on a board. Overlap is permitted; the challenge is to use few sheets or minimize their combined price.

The analogy captures static membership. Real coverage can depend on timing, reliability, capacity or interactions between choices. Those features need additional constraints and may turn the task into a different optimization problem.

Worked example

Why the largest first choice can be misleading

Suppose an invented project must cover requirements {1, 2, 3, 4, 5, 6}. Three available options are A = {1, 2, 3, 4}, B = {1, 2, 5} and C = {3, 4, 6}. All options have equal cost.

The greedy method first selects A because it covers four requirements, more than either alternative. Requirements 5 and 6 remain uncovered. Only B covers 5, and only C covers 6, so the method selects both. Its final cover contains three options.

However, B together with C covers all six requirements using two options. No single option covers the whole universe, so two is optimal. The greedy result is valid but not minimum. Its problem is not that it forgot to update coverage: even with correct updates, the locally largest initial gain led to an inferior combination. This does not mean greedy always performs poorly.

Illustrative case study

Fictional case study: Willow Learning plans a set of workshops. Its first model treats every topic as covered whenever a workshop description mentions it, then chooses a small collection of workshops.

A review finds that several topics receive only a passing mention. The apparent mathematical coverage does not meet the intended training standard. Willow revises the coverage matrix using explicit learning outcomes and checks whether workshops conflict in time or require prerequisites.

The team keeps the original set-cover model as a baseline, then adds the operational constraints needed for the actual decision. The fictional lesson is that an optimal cover of a weakly defined requirement matrix can still fail the business purpose. Correct optimization depends on meaningful inputs, not only an efficient solver.

Common misconceptions and mistakes

A cover must avoid overlap. Ordinary set cover allows repeated coverage; exact cover imposes a different requirement.
Choosing the biggest set first guarantees the fewest sets. Greedy is an approximation method in general.
Minimum means the same as minimal. A cover can be minimal because no selected set can be removed, yet another cover can use fewer sets.
Coverage proves quality. The model establishes membership according to its definitions, not the effectiveness of a test, course or observation process.

Business use

Set cover gives a useful starting point when choices have overlapping capabilities. It makes requirements, option costs and remaining gaps explicit, supporting a clearer discussion than selecting popular options one by one.

Validate the coverage matrix with people who understand the task. Record whether a reported solution is proven optimal, a feasible heuristic result or a solution with a known bound. If requirements need redundancy, capacities, dependencies or time windows, model those explicitly rather than assuming basic set cover already includes them.

Check your understanding

A selected cover uses four sets, and removing any one leaves a gap. Does that prove four is the minimum possible number?

Answer: No. It proves that this cover has no individually removable selected set. A different combination of three or fewer sets might cover everything.

Related terms

Set
Greedy algorithms
greedy algorithm
approximation algorithm
weighted set cover
exact cover
maximum coverage
integer programming
planning heuristic

Learn next

Read greedy algorithm and approximation ratio. Build a small requirement-by-option table, find a greedy cover, and compare it with every possible combination. Then change option costs and explain why the preferred solution may change.

Sources

Avrim Blum, CMU lecture notes on approximation algorithms, set-cover section: https://www.cs.cmu.edu/afs/cs/user/avrim/www/451f12/lectures/lect1106.pdf. Russell and Norvig, Planning, for the relaxed-planning connection and loss of admissibility when using a greedy cover: https://aima.cs.berkeley.edu/newchap11.pdf. Relevant definitions and algorithm discussions were reviewed. The six-requirement example and workshop case are original illustrations.

Previous: Set balancing Next: Set-level