We have a graph with connections to vertices given to us. For example, consider that following pairs of vertices are connected:

1 & 2
2 & 3
3 & 4
4 & 5
5 & 6

Now the graph becomes 1-2-3-4-5-6. Maximum vertices I can drop such that atleast one of their neighbors is still in the set, is: 4. This is because I can drop all but 2 and 5 since everything else has a connection to either 2 or 5.

I am trying to come up with an algorithm that can do this. So far, I have this algorithm:

  1. Get all inputs
  2. Find vertices with maximum connections
  3. Drop all other vertices
  4. Check if all vertices have atleast one neighbor in set
  5. If not, undo last drop

This algorithm is brute force and inefficient. Is there a better way to do it?

  • 2
    $\begingroup$ I am not sure if I understand you correctly. Are you trying to find the complement of a minimum dominating set (en.wikipedia.org/wiki/Dominating_set)? $\endgroup$ – aelguindy Nov 2 '16 at 22:59
  • $\begingroup$ @aelguindy It looks like I am trying to find the complement of a minimum dominating set, though I'm not sure. Consider this: There is a petrol station in every street right now. We are trying to minimize number of petrol stations such that a street has a petrol pump or its neighbor has a petrol pump. $\endgroup$ – learnerX Nov 3 '16 at 1:33
  • $\begingroup$ the description in the comment is too imprecise for me to be able to tell. The dominating set is a set of vertices which is "neighboring" every other vertex in the graph. So if you remove the complement from the graph, leaving the dominating set, then you leave at least one neighbor of each removed vertex. If this matches what you need, then you are trying to find the complement of a minimum dominating set, which is NP-hard, because it's equivalent to finding the minimum dominating set itself. $\endgroup$ – aelguindy Nov 3 '16 at 14:43

Your Answer

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

Browse other questions tagged or ask your own question.