Set Cover Problem In C++

Introduction:

The Set Cover Problem represents a well-known challenge within the realm of computer science and optimization, belonging to the domain of NP-hard problems. This particular problem is classified as a combinatorial optimization dilemma with the objective of identifying the most minimal subset from a specified collection of sets (or universal set). The aim is to ensure that every element within the universal set is encompassed by at least one set within the selected subset.

Program:

#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
using namespace std;
// Function to find the minimum number of subsets to cover the universe
int setCover(const vector<unordered_set<int>>& subsets, const unordered_set<int>& universe) {
    unordered_set<int> elementsCovered;
    vector<int> selectedSets;
    while (elementsCovered.size() < universe.size()) {
        int bestSubset = -1;
        int maxUncovered = -1;
        for (int i = 0; i < subsets.size(); ++i) {
            int uncovered = 0;
            for (int element : subsets[i]) {
                if (elementsCovered.find(element) == elementsCovered.end()) {
                    ++uncovered;
                }
            }
            if (uncovered > maxUncovered) {
                maxUncovered = uncovered;
                bestSubset = i;
            }
        }
        selectedSets.push_back(bestSubset);
        for (int element : subsets[bestSubset]) {
            elementsCovered.insert(element);
        }
    }
    return selectedSets.size();
}
int main() {
    vector<unordered_set<int>> subsets = {{1, 2, 3}, {2, 4}, {3, 5}, {1, 4, 5}};
    unordered_set<int> universe = {1, 2, 3, 4, 5};
    cout << "Minimum number of subsets required: " << setCover(subsets, universe) << endl;
    return 0;
}

Output:

Minimum number of subsets required: 2

Explanation:

• ✅ Problem Overview:

The Set Cover Problem revolves around choosing the most compact group of sets from a specified collection so that each element within a universe is included in at least one set from the selected group. For example, if there is a universe comprising elements {1, 2, 3, 4, 5} and subsets {{1, 2, 3}, {2, 4}, {3, 5}, {1, 4, 5}}, the objective is to determine the minimal number of subsets required to encompass all universe elements.

• ✅ Methodology for Solving:

The algorithm in place adopts a greedy strategy by choosing a subset at each step that includes the highest number of elements not yet covered, ultimately ensuring complete coverage of all elements.

• ✅ Data Structures:

vector<unordered_set<int>> subsets: This specific container stores the subsets, with each subset being depicted as an unsorted collection of integer values. Unordered sets are employed for quick validation of membership.

unordered_set<int> collection: This particular unordered set denotes the complete array of items that must be included within the subsets that are chosen.

• ✅ Primary Objective:

int setCover(const vector<unorderedset<int>>& subsets, const unorderedset<int>& universe): The setCover function accepts a collection of subsets and the universal set as arguments, aiming to determine the smallest number of subsets needed to encompass the entire universe.

unordered_set<int> coveredElements: This container manages elements that have already been included.

vector<int> chosenSets: This container holds the indexes of the chosen subsets.

• ✅ Greedy Selection Approach:

The algorithm continues to iterate until it covers all elements within the universe.

During every iteration, the process involves assessing each subset to determine the one that includes the highest amount of elements that are currently not covered.

It chooses a particular subset and appends its index to the selectedSets list.

The included items are subsequently appended to the elementsCovered list.

Once all components within the cosmos have been accounted for, the function will output the chosen size, indicating the minimal number of subsets needed to encompass the entire universe.

• ✅ Instructions for Implementing the Main Function:

Within the main function, a sample collection of subgroups and the universal set are established.

The setCover function receives these parameters and displays the outcome (the minimum number of necessary subsets).

Complexity analysis:

Time Complexity:

The time complexity of the implemented algorithm depends on the size of the universe and the number of subsets.

• ✅ Let n be the number of elements in the universe, and m be the number of subsets.
• ✅ In the worst-case scenario, the algorithm may iterate through all m subsets to find the one covering the maximum number of uncovered elements. This operation is performed until all elements in the universe are covered.
• ✅ For each iteration, the algorithm potentially checks all n elements in the universe.
• ✅ Therefore, the overall time complexity is O(m⋅n).

Space Complexity:

The space complexity of the algorithm primarily depends on the storage of subsets, universe elements, covered elements, and selected sets.

• ✅ Let you be the maximum number of elements in any subset.
• ✅ The space complexity for storing subsets is O(m⋅u).
• ✅ The space complexity for storing the universe is O(n).
• ✅ In the worst-case scenario, when all elements are distinct, the space complexity for storing covered elements is O(n).
• ✅ The space complexity for storing selected sets is O(k), where k is the minimum number of subsets required to cover the universe.
• ✅ Therefore, the overall space complexity is O(m⋅u+n+k).