The subject of this project was the Minimum Dominating Set problem and this problem has been proven to be NP-complete. It is shown that MDSP could not be solved in polynomial time and could be reduced into Vertex Cover problem which is also an NP-Complete problem. There are many heuristic algorithms that solve this problem in polynomial time. However, these approaches do not guarantee to find optimal solutions. The greedy heuristic approach has been used in this project and this approach does not guarantee to find a minimum dominating set, whereas it guarantees to find a dominating set. The heuristic method is picking a vertex which has the highest degree among uncovered vertices in each iteration, until all vertices are dominated. The time complexity of the algorithm is polynomial which is better than exponential. Furthermore, the theoretical ratio bound is found ln(maximal degree of G) + 2. Experimental running time analysis of heuristic (O(nd+m) theoretically) is calculated with statistics of the running time including mean, standard deviation, standard error, 90% and 95% confidence intervals. The results are demonstrated in charts. Additionally, experimental analysis of correctness is done by starting with assessing the correctness of the heuristic approach that the result found whether is a dominating set or not. Secondly, the results of the both heuristic and exact approach is compared with using charts. Lasty, we have done functional testing on our heuristic algorithm by using Black Box Testing method and generating random graphs. We have provided some of the failed and the successful cases with explanations. It is shown that the quality of the heuristic algorithm is 0.915 and it seems reasonable. Since there is a trade-off between time and the correctness, the heuristic algorithm we experimented on is faster and can be accepted as a result most of the time with a quality of 91.5% correctness.
The heuristic algorithm codes, retrieved January 2, 2021 from https://github.com/oaugusto/DominatingSetHeuristics
The exact algorithm codes, retrieved January 26, 2021 from https://github.com/1ndrew100/graph_theory_smallest_dominating_set