CODEWITHSUNDEEP
javascriptalgorithmgraph-theorygraph-algorithm
Akilan Manivannan
Akilan Manivannan

Reputation: 956

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

Problem Description

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:

Graph

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. This is illustrated below:

Grouped Graph

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.

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.

I would like to see if there is anything that is more efficient/elegant than this approach.

Upvotes: 1

Views: 172

Answers (1)

Vitruvie
Vitruvie

Reputation: 2327

This is the Set Cover Problem, where each set of elements adjacent to a selector is one of the sets in S. This is an NP-complete problem, meaning there is no efficient algorithm that always produces optimal answers. Your suggested solution is the suggested greedy solution to the problem, however it is not guaranteed to give an optimal answer. In general, there will be tradeoffs between optimality and speed for choosing an algorithm for this problem.

Upvotes: 2

Related Questions