A New Approach for Minimum Dominating Set Problem: A Three-Stage Solution with Malatya Centrality Metrics

Year 2025, Volume: 10 Issue: 1, 101 - 115, 01.06.2025

Şeyda Karcı , Fatih Okumuş , İhsan Tuğal , Murat Demir , Ali Karci

Abstract

The Minimum Dominating Set (MDS) problem is a fundamental challenge in graph theory, with applications spanning diverse domains. This study introduces a novel three-stage approach for solving the MDS problem, which yields solutions at each stage of the process. Leveraging three fundamental interconnected Malatya centrality methodologies, the approach offers an effective means of addressing MDS across a spectrum of problem scales. These centrality metrics capture the centrality of the target node with its neighbors. The algorithm prioritizes nodes with elevated dominance and clustering in the initial iterations, gradually incorporating those with lower clustering into the dominant cluster in the later stages. Notably, the transaction cost is higher in the early iterations but decreases in the later ones. The empirical assessment spans various problem scenarios, encompassing synthetic datasets generated through a specific approach, examples crafted using the Erdös-Renyi model, and authentic datasets drawn from network science applications. Upon examination, it becomes evident that the proposed algorithm consistently yields robust solutions across diverse constraints. In the majority of cases, the performance of the proposed methods surpasses that of existing related algorithms. The findings of this study contribute to the evolving landscape of MDS problem-solving techniques, offering insights into the most promising avenues for future research and practical applications in network design, resource allocation, and beyond.

Keywords

Minimum Dominating Set , Domination Number , Centrality , Greedy Heuristics , Graph Algorithms

Minimum hakim küme problemi için yeni bir yaklaşım: Malatya merkezilik metrikleri ile üç aşamalı bir çözüm

Abstract

Minimum Hâkim Küme (MDS) problemi, çeşitli alanlara yayılan uygulamalarla graf teorisinde temel bir zorluktur. Bu çalışma, sürecin her aşamasında çözümler üreten MDS problemini çözmek için yeni bir üç aşamalı yaklaşım sunmaktadır. Üç temel birbirine bağlı Malatya merkezilik metodolojisinden yararlanan yaklaşım, bir dizi problem ölçeğinde MDS'yi ele almanın etkili bir yolunu sunar. Bu merkezilik metrikleri, hedef düğümün komşularıyla olan merkeziliğini yakalar. Algoritma, ilk yinelemelerde yüksek baskınlığa ve kümelenmeye sahip düğümlere öncelik verir ve daha düşük kümelenmeye sahip olanları sonraki aşamalarda kademeli olarak baskın kümeye dahil eder. Dikkat çekici bir şekilde, işlem maliyeti erken yinelemelerde daha yüksekken sonraki yinelemelerde azalır. Ampirik değerlendirme, belirli bir yaklaşımla oluşturulan sentetik veri kümelerini, Erdös-Renyi modeli kullanılarak hazırlanmış örnekleri ve ağ bilimi uygulamalarından alınan otantik veri kümelerini kapsayan çeşitli problem senaryolarını kapsar. İnceleme sonucunda önerilen algoritmanın çeşitli kısıtlamalar arasında tutarlı bir şekilde sağlam çözümler ürettiği ortaya çıkar. Çoğu durumda, önerilen yöntemlerin performansı mevcut ilgili algoritmaların performansını aşar. Bu çalışmanın bulguları, MDS problem çözme tekniklerinin gelişen manzarasına katkıda bulunarak, ağ tasarımı, kaynak tahsisi ve ötesinde gelecekteki araştırmalar ve pratik uygulamalar için umut verici yollara dair içgörüler sunar.

Keywords

Minimum Hakim Küme , Hakim Düğüm Sayısı , Merkezilik , Açgözlü Sezgisel Yöntemler , Graf Algoritmaları

References

• Abed, S. A., & Rais, H. M. (2017). Hybrid bat algorithm for minimum dominating set problem. Journal of Intelligent & Fuzzy Systems, 33(4), 2329–2339. https://doi.org/10.3233/JIFS-17398
• Aggarwal, C., Subbian, K., Butler, K., Stephens, M., Stephens, M., Chakrabarti, D., Kumar, R., Tomkins, A., Clauset, A., Moore, C., Newman, M. E. J., Csardi, G., Nepusz, T., Decelle, A., Krzakala, F., Moore, C., Zdeborov??, L., Eisinga, R., Te Grotenhuis, M., … Cov, E. R. (2014). {SNAP Datasets}: {Stanford} Large Network Dataset Collection. Physical Review Letters, Complex Sy(1).
• Albuquerque, M., & Vidal, T. (2018). An efficient matheuristic for the minimum-weight dominating set problem. Applied Soft Computing Journal, 72. https://doi.org/10.1016/j.asoc.2018.06.052
• Batool, K., & Niazi, M. A. (2014). Towards a methodology for validation of centrality measures in complex networks. PLoS ONE, 9(4). https://doi.org/10.1371/journal.pone.0090283
• Brin, S., & Page, L. (1998). The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30(1–7), 107–117. https://doi.org/10.1016/S0169-7552(98)00110-X
• Bujtás, C., & Klavžar, S. (2016). Improved Upper Bounds on the Domination Number of Graphs With Minimum Degree at Least Five. Graphs and Combinatorics, 32(2), 511–519. https://doi.org/10.1007/s00373-015-1585-7
• Casado, A., Bermudo, S., López-Sánchez, A. D., & Sánchez-Oro, J. (2023). An iterated greedy algorithm for finding the minimum dominating set in graphs. Mathematics and Computers in Simulation, 207. https://doi.org/10.1016/j.matcom.2022.12.018
• Chalupa, D. (2018). An order-based algorithm for minimum dominating set with application in graph mining. Information Sciences, 426. https://doi.org/10.1016/j.ins.2017.10.033
• Connolly, S., Gabor, Z., Godbole, A., Kay, B., & Kelly, T. (2016). Bounds on the maximum number of minimum dominating sets. Discrete Mathematics, 339(5). https://doi.org/10.1016/j.disc.2015.12.030
• Erdös, P., & Rényi, A. (1959). On random graphs. Publicationes Mathematicae, 6, 290–297. https://doi.org/10.2307/1999405
• Esfahanian, A. (2013). Connectivity algorithms. In Topics in structural graph theory (pp. 268–281). Cambridge University Press. https://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
• Estrada, E. (2011). The Structure of Complex Networks. In SIAM Review (Vol. 45, Issue 2). https://doi.org/10.1093/acprof:oso/9780199591756.001.0001
• Gao, C., Lan, X., Zhang, X., & Deng, Y. (2013). A Bio-Inspired Methodology of Identifying Influential Nodes in Complex Networks. PLoS ONE, 8(6). https://doi.org/10.1371/journal.pone.0066732
• Hedar, A. R., & Ismail, R. (2010). Hybrid genetic algorithm for minimum dominating set problem. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 6019 LNCS(PART 4). https://doi.org/10.1007/978-3-642-12189-0_40
• Hernández Mira, F. Á., Parra Inza, E., Sigarreta Almira, J. M., & Vakhania, N. (2022). A polynomial-time approximation to a minimum dominating set in a graph. Theoretical Computer Science, 930, 142–156. https://doi.org/10.1016/j.tcs.2022.07.020
• Hu, J., Du, Y., Mo, H., Wei, D., & Deng, Y. (2016). A modified weighted TOPSIS to identify influential nodes in complex networks. Physica A: Statistical Mechanics and Its Applications, 444, 73–85. https://doi.org/10.1016/j.physa.2015.09.028
• Jovanovic, R., & Tuba, M. (2013). Ant colony optimization algorithm with pheromone correction strategy for the minimum connected dominating set problem. Computer Science and Information Systems, 10(1). https://doi.org/10.2298/CSIS110927038J
• Kapoor, K., Sharma, D., & Srivastava, J. (2013). Weighted node degree centrality for hypergraphs. Proceedings of the 2013 IEEE 2nd International Network Science Workshop, NSW 2013. https://doi.org/10.1109/NSW.2013.6609212
• Karci, A. (2020). New Algorithms for Minimum Dominating Set in Any Graphs. Computer Science, 5(2).
• Karcı, A., Yakut, S., & Öztemiz, F. (2022). A New Approach Based on Centrality Value in Solving the Minimum Vertex Cover Problem: Malatya Centrality Algorithm. Computer Science. https://doi.org/10.53070/bbd.1195501
• Kunegis, J. (2013). KONECT - The koblenz network collection. WWW 2013 Companion - Proceedings of the 22nd International Conference on World Wide Web.
• Li, J., Potru, R., & Shahrokhi, F. (2020). A Performance Study of Some Approximation Algorithms for Computing a Small Dominating Set in a Graph. Algorithms, 13(12), 339. https://doi.org/10.3390/a13120339
• Newman, M. E. J. (2003). The Structure and Function of Complex Networks. SIAM Review, 45(2), 167–256.
• Nguyen, M. H., Hà, M. H., Nguyen, D. N., & Tran, T. T. (2020). Solving the k-dominating set problem on very large-scale networks. Computational Social Networks, 7(1). https://doi.org/10.1186/s40649-020-00078-5
• Okumuş, F., & Karcı, Ş. (2024). MDSA: A Dynamic and Greedy Approach to Solve the Minimum Dominating Set Problem. Applied Sciences, 14(20), 9251. https://doi.org/10.3390/app14209251
• Ore, O. (1962). Theory of Graphs. American Mathematical Society Colloquium Publications.
• Page, L., Brin, S., Motwani, R., & Winograd, T. (1998). The PageRank Citation Ranking: Bringing Order to the Web. World Wide Web Internet And Web Information Systems, 54(1999–66), 1–17. https://doi.org/10.1.1.31.1768
• Potluri, A., & Singh, A. (2013). Hybrid metaheuristic algorithms for minimum weight dominating set. Applied Soft Computing Journal, 13(1). https://doi.org/10.1016/j.asoc.2012.07.009
• Potluri, A., & Singh, A. (2011). Two hybrid meta-heuristic approaches for minimum dominating set problem. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7077 LNCS(PART 2). https://doi.org/10.1007/978-3-642-27242-4_12
• Sanchis, L. A. (2002). Experimental Analysis of Heuristic Algorithms for the Dominating Set Problem. Algorithmica, 33(1), 3–18. https://doi.org/10.1007/s00453-001-0101-z
• Truta, T. M., Campan, A., & Beckerich, M. (2020). Efficient Approximation Algorithms for Minimum Dominating Sets in Social Networks. In Research Anthology on Artificial Intelligence Applications in Security (pp. 1120–1153). IGI Global. https://doi.org/10.4018/978-1-7998-7705-9.ch052
• Tuğal, İ., & Karcı, A. (2019). Comparisons of Karcı and Shannon entropies and their effects on centrality of social networks. Physica A: Statistical Mechanics and Its Applications, 523, 352–363. https://doi.org/10.1016/j.physa.2019.02.026
• Tuğal, İhsan, & Karcı, A. (2020). Determination of Influential Countries by Cultural and Geographical Parameters. Anemon Muş Alparslan University Social Sciences Journal. https://doi.org/10.18506/anemon.563211
• Vazirani, V. V. (2003). Approximation Algorithms. Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-662-04565-7
• Wang, F., Du, H., Camacho, E., Xu, K., Lee, W., Shi, Y., & Shan, S. (2011). On positive influence dominating sets in social networks. Theoretical Computer Science, 412(3), 265–269. https://doi.org/10.1016/j.tcs.2009.10.001
• Yakut, S., Öztemiz, F., & Karci, A. (2023). A new robust approach to solve minimum vertex cover problem: Malatya vertex-cover algorithm. The Journal of Supercomputing. https://doi.org/10.1007/s11227-023-05397-8
• Zhou, Y., Lv, G., Xiu, B., Zhang, W., & Cheng, Q. (2014). A faster approximate method to identify minimum dominating set. Proceedings of the IEEE International Conference on Software Engineering and Service Sciences, ICSESS. https://doi.org/10.1109/ICSESS.2014.6933601