3
$\begingroup$

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:

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. I only want the selectors 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.

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.

$\endgroup$
2
3
$\begingroup$

Your problem can be equivalently stated as a set cover problem. The universal set $U$ is composed of all elements $e_1,\dotsc,e_n$. For every node $s_i$ define a subset $S_i$ of $U$ that contains the elements it is connected to. For example: $S_{1} = \{e_1,e_2,e_3\}$ from the the example given in the question. Let $\mathcal{C}$ be the collection of all such subsets. Now, the task is to pick the minimum number of subsets whose union gives the set $U$.

The best possible polynomial-time algorithm for the set cover problem is the greedy algorithm only. It the same as the one you mentioned in your question. It gives $\Theta(\log n)$-approximation guarantee. Note that it is $\mathsf{NP}$-hard to approximate set cover with better than $\log n$ factor (see this). So this is the best possible approximation guarantee that you can achieve.

I know that the greedy algorithm is quite simple but that is the beauty.

$\endgroup$
3
  • 1
    $\begingroup$ In practice, it might also be a good idea to run some metaheuristics (e.g., genetic algorithm) in addition to the approximation algorithm with a guarantee, if there are no strict time constraints. After running all possible methods, one can pick the the best solution. $\endgroup$ – Juho Jun 17 at 5:27
  • $\begingroup$ I had a feeling that it would end up being some sort of Cover type of problem. Just out of curiosity, what is the algorithm complexity? It seems like it would be pretty terrible but I'm not sure. $\endgroup$ – Akilan Manivannan Jun 17 at 14:08
  • $\begingroup$ @AkilanManivannan Is your question is to Juho or me? The running time complexity of greedy algorithm is already given in this link. It is $O(|E|)$, where $|E|$ are the number of edges in the graph. $\endgroup$ – Inuyasha Yagami Jun 17 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.