1

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

knewit
  • 55
  • 1
  • 6

1 Answers1

2

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.

zohar.kom
  • 1,765
  • 3
  • 12
  • 28
  • I actually don't think this provides a (1+log|V|) approximation. You probably adapted the greedy approach for dominating set (without the "independent" part) thinking it would work out the same here but the analysis breakes down if you delete the neighbours as you do in step 2. Minimum independent dominating set (or equivalently minimum maximal independent set) is actually notoriously difficult to approximate (no |V|^(1-epsilon) approximation in poly-time unless P=NP). – Tassle Mar 24 '21 at 16:53