SavedAdd your journal

Journals / Firat University Journal of Experimental and Computational Engineering / 2026 / Cilt: 5 Sayı: 3

A Systematic Experimental Comparison of Exact, Greedy, Local Search, Metaheuristic, and Distributed Algorithms for the Minimum Dominating Set Problem

Minimum Baskın Küme Problemi için Kesin, Açgözlü, Yerel Arama, Metasezgisel ve Dağıtık Algoritmaların Sistematik Deneysel Karşılaştırması

Furkan Öztemiz(İNÖNÜ ÜNİVERSİTESİ)0000-0001-5425-3474
Selman Yakut(İNÖNÜ ÜNİVERSİTESİ)0000-0002-0649-1993
Pages
907–927
Publication Date
2026-10-25
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

The results reveal in detail the trade-offs in solution quality, runtime, and memory usage between different algorithms.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:The Minimum Dominating Set (MDS) problem is an NP-hard optimization problem that aims to find the smallest dominating set of nodes encompassing all nodes of a graph.
📊
Key Findings & Data:Because it is equivalent to the cluster covering problem, approximate solutions better than the multiplier (1−ε)lnn cannot be obtained in polynomial time unless P = NP.
💡
Conclusion & Impact:The results reveal in detail the trade-offs in solution quality, runtime, and memory usage between different algorithms.
🔬Design:Modeling & Simulation
📍Scope:Comprehensive Sample
⚙️Variables:Minimum baskın küme · Tamsayılı doğrusal programlama · Metasezgisel optimizasyon

Abstract

The Minimum Dominating Set (MDS) problem is an NP-hard optimization problem that aims to find the smallest dominating set of nodes encompassing all nodes of a graph. Because it is equivalent to the cluster covering problem, approximate solutions better than the multiplier (1−ε)lnn cannot be obtained in polynomial time unless P = NP. This work presents a comprehensive comparison of ten representative methods selected from six algorithm families (exact ILP, greedy and degree-based heuristics, configuration-controlled local search, genetic algorithm, ant colony optimization, binary particle swarm optimization, simulated annealing, enhanced binary whale optimizer, and synchronous distributed greedy algorithm) in a single, reproducible experimental framework. Experiments were performed on a total of 110 benchmark graphs consisting of five real-world networks and nine random graph models; stochastic methods were evaluated with 30 independent runs, and ILP optima were used as a quality reference. Statistical analyses show significant performance differences between the algorithms (Friedman χ²(9) = 69.6, p = 1.8×10⁻¹¹). Configuration-checking local search was the most successful approximate method, reaching the optimum solution in most instances, followed closely by ant colony optimization and genetic algorithm. While exact ILP produced fast solutions up to approximately 200 nodes, it ran into time constraints in larger and denser graphs; at these scales, metaheuristic methods were the most feasible option. Furthermore, it was shown that the genetic algorithm could be sped up by 1.7–2.5× with parallelization, while the distributed algorithm could operate with low communication costs in large-scale networks with an approximately 14% loss in solution quality.. The results reveal in detail the trade-offs in solution quality, runtime, and memory usage between different algorithms.

Özet

Minimum baskın küme (MDS) problemi, bir grafın tüm düğümlerini kapsayan en küçük baskın düğüm kümesini bulmayı amaçlayan NP-zor bir optimizasyon problemidir. Küme örtme problemine eşdeğer olması nedeniyle, P = NP olmadıkça polinom zamanda (1−ε)lnn çarpanından daha iyi yaklaşık çözümler elde edilememektedir. Bu çalışma, altı algoritma ailesinden seçilen on temsilî yöntemin (kesin ILP, açgözlü ve derece-tabanlı sezgiseller, yapılandırma-denetimli yerel arama, genetik algoritma, karınca kolonisi optimizasyonu, ikili parçacık sürü optimizasyonu, tavlama benzetimi, geliştirilmiş ikili balina optimize edici ve senkron dağıtık açgözlü algoritma) tek ve yeniden üretilebilir bir deneysel çerçevede kapsamlı karşılaştırmasını sunmaktadır. Deneyler, beş gerçek dünya ağı ve dokuz rastgele graf modelinden oluşan toplam 110 kıyaslama grafı üzerinde gerçekleştirilmiş; stokastik yöntemler 30 bağımsız çalıştırma ile değerlendirilmiş ve ILP optimumları kalite referansı olarak kullanılmıştır. İstatistiksel analizler algoritmalar arasında anlamlı performans farkları olduğunu göstermektedir (Friedman χ²(9) = 69.6, p = 1,8×10⁻¹¹). Yapılandırma-denetimli yerel arama, çoğu örnekte optimum çözüme ulaşarak en başarılı yaklaşık yöntem olurken, karınca kolonisi optimizasyonu ve genetik algoritma onu yakından takip etmiştir. Kesin ILP yaklaşık 200 düğüme kadar hızlı çözümler üretirken, daha büyük ve yoğun graflarda süre sınırına takılmış; bu ölçeklerde metasezgisel yöntemler en uygulanabilir seçenek olmuştur. Ayrıca genetik algoritmanın paralelleştirme ile 1,7–2,5× hızlanabildiği, dağıtık algoritmanın ise yaklaşık %14 çözüm kalitesi kaybı karşılığında büyük ölçekli ağlarda düşük iletişim maliyetiyle çalışabildiği gösterilmiştir. Sonuçlar, farklı algoritmalar arasındaki çözüm kalitesi, çalışma süresi ve bellek kullanımı ödünleşimlerini ayrıntılı biçimde ortaya koymaktadır.

🔖

Cite This Article

Öztemiz, F., Yakut, S. (2026). A Systematic Experimental Comparison of Exact, Greedy, Local Search, Metaheuristic, and Distributed Algorithms for the Minimum Dominating Set Problem. Firat University Journal of Experimental and Computational Engineering, Cilt: 5 Sayı: 3, 907–927. https://doi.org/10.62520/fujece.2020431

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (49)

  1. T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of Domination in Graphs. New York, NY, USA: Marcel Dekker, 1998.
  2. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco, CA, USA: W. H. Freeman, 1979.
  3. D. S. Johnson, “Approximation algorithms for combinatorial problems,” J. Comput. Syst. Sci., vol. 9, no. 3, pp. 256–278, 1974.
  4. V. Chvátal, “A greedy heuristic for the set-covering problem,” Math. Oper. Res., vol. 4, no. 3, pp. 233–235, 1979.
  5. A. K. Parekh, “Analysis of a greedy heuristic for finding small dominating sets in graphs,” Inf. Process. Lett., vol. 39, no. 5, pp. 237–240, 1991.
  6. U. Feige, “A threshold of ln n for approximating set cover,” J. ACM, vol. 45, no. 4, pp. 634–652, 1998.
  7. I. Dinur and D. Steurer, “Analytical approach to parallel repetition,” in Proc. 46th Annu. ACM Symp. Theory Comput. (STOC), 2014, pp. 624–633.
  8. L. Jia, R. Rajaraman, and T. Suel, “An efficient distributed algorithm for constructing small dominating sets,” Distrib. Comput., vol. 15, no. 4, pp. 193–205, 2002.
  9. F. Kuhn and R. Wattenhofer, “Constant-time distributed dominating set approximation,” in Proc. 22nd Annu. ACM Symp. Principles Distrib. Comput. (PODC), 2003, pp. 25–32.
  10. F. V. Fomin, F. Grandoni, and D. Kratsch, “A measure & conquer approach for the analysis of exact algorithms,” J. ACM, vol. 56, no. 5, Art. no. 25, 2009.
  11. J. M. M. van Rooij and H. L. Bodlaender, “Exact algorithms for dominating set,” Discrete Appl. Math., vol. 159, no. 17, pp. 2147–2164, 2011.
  12. R. G. Downey and M. R. Fellows, Parameterized Complexity. New York, NY, USA: Springer, 1999.
  13. B. S. Baker, “Approximation algorithms for NP-complete problems on planar graphs,” J. ACM, vol. 41, no. 1, pp. 153–180, 1994.
  14. L. A. Sanchis, “Experimental analysis of heuristic algorithms for the dominating set problem,” Algorithmica, vol. 33, no. 1, pp. 3–18, 2002.
  15. D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning. Reading, MA, USA: Addison-Wesley, 1989.
  16. J. E. Beasley and P. C. Chu, “A genetic algorithm for the set covering problem,” Eur. J. Oper. Res., vol. 94, no. 2, pp. 392–404, 1996.
  17. S. N. Chaurasia and A. Singh, “A hybrid evolutionary algorithm with guided mutation for minimum weight dominating set,” Appl. Intell., vol. 43, no. 3, pp. 512–529, 2015.
  18. A. Potluri and A. Singh, “Hybrid metaheuristic algorithms for minimum weight dominating set,” Appl. Soft Comput., vol. 13, no. 1, pp. 76–88, 2013.
  19. M. Dorigo and T. Stützle, Ant Colony Optimization. Cambridge, MA, USA: MIT Press, 2004.
  20. J. Kennedy and R. Eberhart, “Particle swarm optimization,” in Proc. IEEE Int. Conf. Neural Networks, 1995, pp. 1942–1948.
  21. J. Kennedy and R. C. Eberhart, “A discrete binary version of the particle swarm algorithm,” in Proc. IEEE Int. Conf. Syst., Man, Cybern., 1997, pp. 4104–4108.
  22. G. Lin and J. Guan, “A binary particle swarm optimization for the minimum weight dominating set problem,” J. Comput. Sci. Technol., vol. 33, no. 2, pp. 305–322, 2018.
  23. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671–680, 1983.
  24. A. R. Hedar and R. Ismail, “Simulated annealing with stochastic local search for minimum dominating set problem,” Int. J. Mach. Learn. Cybern., vol. 3, no. 2, pp. 97–109, 2012.
  25. E. Alba and J. M. Troya, “A survey of parallel distributed genetic algorithms,” Complexity, vol. 4, no. 4, pp. 31–52, 1999.
  26. E. Cantú-Paz, Efficient and Accurate Parallel Genetic Algorithms. Boston, MA, USA: Kluwer Academic Publishers, 2000.
  27. S. Cai, W. Hou, Y. Wang, C. Luo, and Q. Lin, “Two-goal local search and inference rules for minimum dominating set,” in Proc. 29th Int. Joint Conf. Artif. Intell. (IJCAI), 2020, pp. 1467–1473.
  28. S. Mirjalili and A. Lewis, “The whale optimization algorithm,” Adv. Eng. Softw., vol. 95, pp. 51–67, 2016.
  29. B. Zouilekh and S. Bouroubi, “Optimizing minimum dominating set using an enhanced binary whale algorithm,” J. Inf. Optim. Sci., vol. 47, no. 3, pp. 887–905, 2026.
  30. A. Kothapalli, M. Shabbir, and X. Koutsoukos, “Learning-based heuristic for combinatorial optimization of the minimum dominating set problem using graph convolutional networks,” arXiv preprint arXiv:2306.03434, 2023. [Online]. Available: https://arxiv.org/abs/2306.03434.
  31. D. Zhang, H. Dai, N. Malkin, A. Courville, Y. Bengio, and L. Pan, “Let the flows tell: Solving graph combinatorial optimization problems with GFlowNets,” in Adv. Neural Inf. Process. Syst., vol. 36, pp. 11952–11969, 2023.
  32. W. W. Zachary, “An information flow model for conflict and fission in small groups,” J. Anthropol. Res., vol. 33, no. 4, pp. 452–473, 1977.
  33. D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson, “The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations,” Behav. Ecol. Sociobiol., vol. 54, no. 4, pp. 396–405, 2003.
  34. D. E. Knuth, The Stanford GraphBase: A Platform for Combinatorial Computing. New York, NY, USA: ACM Press, 1994.
  35. V. Krebs, “Books about US politics,” unpublished network dataset, 2004. [Online]. Available: http://www.orgnet.com/.
  36. M. Girvan and M. E. J. Newman, “Community structure in social and biological networks,” Proc. Natl. Acad. Sci. USA, vol. 99, no. 12, pp. 7821–7826, 2002.
  37. P. Erdős and A. Rényi, “On random graphs I,” Publ. Math. Debrecen, vol. 6, pp. 290–297, 1959.
  38. A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, no. 5439, pp. 509–512, 1999.
  39. D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’ networks,” Nature, vol. 393, no. 6684, pp. 440–442, 1998.
  40. J. Demšar, “Statistical comparisons of classifiers over multiple data sets,” J. Mach. Learn. Res., vol. 7, pp. 1–30, 2006.
  41. A. A. Hagberg, D. A. Schult, and P. J. Swart, “Exploring network structure, dynamics, and function using NetworkX,” in Proc. 7th Python Sci. Conf. (SciPy), 2008, pp. 11–15.
  42. C. R. Harris et al., “Array programming with NumPy,” Nature, vol. 585, no. 7825, pp. 357–362, 2020.
  43. P. Virtanen et al., “SciPy 1.0: Fundamental algorithms for scientific computing in Python,” Nat. Methods, vol. 17, no. 3, pp. 261–272, 2020.
  44. S. Mitchell, M. O’Sullivan, and I. Dunning, “PuLP: A linear programming toolkit for Python,” Dept. Eng. Sci., Univ. Auckland, Auckland, New Zealand, 2011.
  45. M. Penrose, Random Geometric Graphs. Oxford, U.K.: Oxford Univ. Press, 2003.
  46. P. Holme and B. J. Kim, “Growing scale-free networks with tunable clustering,” Phys. Rev. E, vol. 65, no. 2, Art. no. 026107, 2002.
  47. A. Steger and N. C. Wormald, “Generating random regular graphs quickly,” Combin. Probab. Comput., vol. 8, no. 4, pp. 377–396, 1999.
  48. B. M. Waxman, “Routing of multipoint connections,” IEEE J. Sel. Areas Commun., vol. 6, no. 9, pp. 1617–1622, 1988.
  49. P. W. Holland, K. B. Laskey, and S. Leinhardt, “Stochastic blockmodels: First steps,” Social Netw., vol. 5, no. 2, pp. 109–137, 1983.