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
S1, we still need to include
S4 because of the
E6 nodes. In other words, these groups do not need to be exact covers and can overlap if necessary.
After some research, I've heard that this might be a version of the Dominating Set Problem. Maybe that helps?
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.