# Minimum number of groups such that every element in graph is included?

## Problem Description

Note: I originally posted this question on Stack Overflow but was referred to this community instead.

I have a graph containing selectors and elements. An element can have multiple selectors associated with it. As a graph, it looks something like this:

In the example, any node prefixed with an S is a selector and any node prefixed with an E is an element.

As you can see, elements can only connect with selectors. No elements will be connected with elements and no selectors will be connected to other selectors.

I want to choose the minimum number of selectors such that their neighbors include every element in the graph. In the above example, I would want my algorithm to return `S1, S3, S4`. However, I don’t need to return the groups that they represent. I only want the selectors This is illustrated below:

In the example, we do not need to use the `S2` selector as it is redundant. Furthermore, even though `E1` occurs in both `S4` and `S1`, we still need to include `S4` because of the `E5` and `E6` nodes. In other words, these groups do not need to be exact covers and can overlap if necessary.

Edit: After some research, I’ve heard that this might be a version of the Dominating Set Problem. Maybe that helps?

## Possible Solution

Greedily, I could create an adjacency list of the selectors and the elements that are connected to them and select the selector with the largest elements. Then I could eliminate the elements from every other node’s list and repeat the process until I have no elements left.

## What I’m Looking For

I would like to see if there is anything that is more efficient/elegant than this approach. Even if it ends up being NP-Complete or NP-Hard, I am sure that there is a better algorithm than the greedy approach that I outlined above.

I’m also open to suggestions about the different ways I could frame this problem or how I should title it so that it is more clear to other readers.