Algorithmic and Applied Aspects of Network Domination

Project Description: This project explores various domination problems in graphs, including the classic Dominating Set problem, the Connected Dominating Set problem, and Roman Domination Functions. Our study explores a wide range of algorithmic approaches, from optimization and enumeration techniques to parameterized complexity analysis, identifying cases where these problems become more tractable. We also investigate efficient algorithms for special graph classes. In addition to theoretical work, we examine real-world applications of domination-related problems, particularly in biological networks (e.g., controllability analysis) and social networks (e.g., influence propagation). By combining the study of (theoretical) graph algorithms with practical applications, this research contributes to both foundational and applied domains of network science and data analysis.

PI: Faisal N. Abu-Khzam

Publications:

F. Abu-Khzam, H. Fernau, B. Gras, M. Liedloff and K. Mann. Enumerating Connected Dominating Sets. SIAM Journal on Discrete Mathematics, 2025. Accepted for publication.

F. N. Abu-Khzam and L. Isenmann. Domination in Diameter-Two Graphs and the 2-Club Cluster Vertex Deletion Parameter, in proceedings of the International Joint Conference on Theoretical Computer Science - Frontier of Algorithmic Wisdom (IJTCS-FAW), 2025. Accepted for publication.

F. N. Abu-Khzam, H. Fernau and K. Mann. Minimal Roman dominating functions: extensions and enumeration, Algorithmica 86(6): 1862-1887 (2024).

F. N. Abu-Khzam, G. Bou Matar and S. Thoumi. Pack and Measure: An Effective Approach for Influence Propagation in Social Networks. CoRR abs/2401.00525 (2024)

M. El Sahili and F. N. Abu-Khzam. A Linear Kernel for Planar Vector Domination. CoRR abs/2312.09374 (2023)

F. N. Abu-Khzam, H. Fernau and K. Mann. Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes. in proceedings of the 48th Intl. Symp. on Mathematical Foundations of Computer Science (MFCS), LIPIcs 272, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023: 6:1-6:15

F. N. Abu-Khzam. An improved exact algorithm for minimum dominating set in chordal graphs, Information Processing Letters 174: 106206 (2022).

S. K. Grady, F. N. Abu-Khzam, R. D. Hagan, H. Shams and M. A. Langston. Domination based classification algorithms for the controllability analysis of biological interaction networks, Scientific Reports 12, 11897 (2022).

Previous publications (from related older projects):

F. N. Abu-Khzam and K. Lamaa. Efficient Heuristic Algorithms for Positive-Influence Dominating Set in Social Networks. Proceedings, the IEEE Conference on Computer Communications Workshops, (INFOCOM) 2018: 610-615.

F. N. Abu-Khzam, S. Cai, J. Egan, P. Shaw and K. Wang. Turbo-charging Dominating Set with an FPT Subroutine: Further Improvements and Experimental Analysis. 13th annual conference on Theory and Applications of Models of Computation (TAMC), Lecture Notes in Computer Science (LNCS 10185), Springer 2017: 59-70.

F. N. Abu-Khzam and P. Heggernes: Enumerating minimal dominating sets in chordal graphs. Information Processing Letters 116(12): 739-743 (2016)

F. N. Abu-Khzam, C. Bazgan, M. Chopin and H. Fernau. Data reductions and combinatorial bounds for improved approximation algorithms, Journal of Computer and Systems Science, 82(3): 503-520 (2016)

F. N. Abu-Khzam, A. E. Mouawad and M. Liedloff. An Exact Algorithm for Connected Red-Blue Dominating Set. Journal of Discrete Algorithms, volume 9(3): 252-262, 2011.