python - Finding minimum indepedent dominating set using a greedy algorithm

1
votes

I developed an algorithm that finds the minimum independent dominating set of a graph based on a distance constraint. (I used Python and NetworkX to generate graphs and get the pairs)

The algorithm uses a brute force approach:

  • Find all possible pairs of edges
  • Check which nodes satisfy the distance constraint
  • Find all possible independent dominating sets
  • Compare the independent dominating sets found and find the minimum dominating set

For small number of nodes it wouldnt make a difference but for large numbers the program is really slow.

Is there any way that I could make it run faster using a different approach?

Thanks

1
pythonalgorithmgraph-theorynetworkxindependent-set
Are you open to using an integer program solver? – David Eisenstat

1 Answers

2
votes

Unfortunately, the problem of finding the minimum independent dominating set is NP-complete. Hence, any known algorithm which is sound and complete will be inefficient.

A possible approach is to use an incomplete algorithm (aka local search). For example, the following algorithm is known to have a factor (1 + log|V|) approximation:

1. Choose a node with the maximal number of neighbors and add it to the dominating set.
2. Remove the node and all of it's neighbors from the graph.
3. Repeat until there are no more nodes in the graph.