Document Open Access Logo

Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes

Authors Faisal N. Abu-Khzam , Henning Fernau , Kevin Mann

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2023.6.pdf
  • Filesize: 0.76 MB
  • 15 pages

Document Identifiers

Author Details

Faisal N. Abu-Khzam
  • Department of Computer Science and Mathematics, Lebanese American University, Beirut, Lebanon
Henning Fernau
  • Fachbereich IV, Informatikwissenschaften, Universität Trier, Germany
Kevin Mann
  • Fachbereich IV, Informatikwissenschaften, Universität Trier, Germany

Cite As Get BibTex

Faisal N. Abu-Khzam, Henning Fernau, and Kevin Mann. Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.MFCS.2023.6

Abstract

The concept of Roman domination has recently been studied concerning enumerating and counting in F. N. Abu-Khzam et al. (WG 2022). More technically speaking, a function that assigns 0,1,2 to the vertices of an undirected graph is called a Roman dominating function if each vertex assigned zero has a neighbor assigned two. Such a function is called minimal if decreasing any assignment to any vertex would yield a function that is no longer a Roman dominating function. It has been shown that minimal Roman dominating functions can be enumerated with polynomial delay, i.e., between any two outputs of a solution, no more than polynomial time will elapse. This contrasts what is known about minimal dominating sets, where the question whether or not these can be enumerated with polynomial delay is open for more than 40 years. This makes the concept of Roman domination rather special and interesting among the many variants of domination problems studied in the literature, as it has been shown for several of these variants that the question of enumerating minimal solutions is tightly linked to that of enumerating minimal dominating sets, see M. Kanté et al. in SIAM J. Disc. Math., 2014. The running time of the mentioned enumeration algorithm for minimal Roman dominating functions (Abu-Khzam et al., WG 2022) could be estimated as 𝒪(1.9332ⁿ) on general graphs of order n. Here, we focus on special graph classes, as has been also done for enumerating minimal dominating sets before. More specifically, for chordal graphs, we present an enumeration algorithm running in time 𝒪(1.8940ⁿ). It is unknown if this gives a tight bound on the maximum number of minimal Roman dominating functions in chordal graphs. For interval graphs, we can lower this time bound further to 𝒪(1.7321ⁿ), which also matches the known lower bound concerning the maximum number of minimal Roman dominating functions. We can also provide a matching lower and upper bound for forests, which is (incidentally) the same, namely 𝒪^*(√3ⁿ). Furthermore, we present an optimal enumeration algorithm running in time 𝒪^*(∛3ⁿ) for split graphs and for cobipartite graphs, i.e., we can also give a matching lower bound example for these graph classes. Hence, our enumeration algorithms for interval graphs, forests, split graphs and cobipartite graphs are all optimal. The importance of our results stems from the fact that, for other types of domination problems, optimal enumeration algorithms are not always found.
Interestingly, we use a different form of analysis for the running times of our different algorithms, and the branchings had to be tailored and tweaked to obtain the intended optimality results. Our Roman dominating functions enumeration algorithm for trees and forests is distinctively different from the one for minimal dominating sets by Rote (SODA 2019).Our approach also allows to give concrete formulas for counting minimal Roman dominating functions on more concrete graph families like paths.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • special graph classes
  • counting problems
  • enumeration problems
  • domination problems
  • Roman domination

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. F. N. Abu-Khzam, C. Bazgan, M. Chopin, and H. Fernau. Data reductions and combinatorial bounds for improved approximation algorithms. Journal of Computer and System Sciences, 82(3):503-520, 2016. Google Scholar
  2. F. N. Abu-Khzam, H. Fernau, and K. Mann. Minimal Roman dominating functions: Extensions and enumeration. Technical Report 2204.04765, Cornell University, ArXiv/CoRR, 2022. URL: https://doi.org/10.48550/arXiv.2204.04765.
  3. F. N. Abu-Khzam, H. Fernau, and K. Mann. Minimal Roman dominating functions: Extensions and enumeration. In M. A. Bekos and M. Kaufmann, editors, Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG, volume 13453 of LNCS, pages 1-15. Springer, 2022. URL: https://doi.org/10.1007/978-3-031-15914-5_1.
  4. F. N. Abu-Khzam, H. Fernau, and K. Mann. Roman census: Enumerating and counting Roman dominating functions on graph classes. Technical Report 2208.05261, Cornell University, ArXiv/CoRR, 2022. URL: https://arxiv.org/abs/2208.05261.
  5. F. N. Abu-Khzam and P. Heggernes. Enumerating minimal dominating sets in chordal graphs. Information Processing Letters, 116(12):739-743, 2016. Google Scholar
  6. C. Bazgan, L. Brankovic, K. Casel, H. Fernau, K. Jansen, K.-M. Klein, M. Lampis, M. Liedloff, J. Monnot, and V. Paschos. The many facets of upper domination. Theoretical Computer Science, 717:2-25, 2018. Google Scholar
  7. S. Benecke. Higher order domination of graphs. Master’s thesis, Department of Applied Mathematics of the University of Stellebosch, South Africa, http://dip.sun.ac.za/~vuuren/Theses/Benecke.pdf, 2004.
  8. S. Bermudo and H. Fernau. Computing the differential of a graph: hardness, approximability and exact algorithms. Discrete Applied Mathematics, 165:69-82, 2014. Google Scholar
  9. S. Bermudo and H. Fernau. Combinatorics for smaller kernels: The differential of a graph. Theoretical Computer Science, 562:330-345, 2015. Google Scholar
  10. S. Bermudo, H. Fernau, and J. M. Sigarreta. The differential and the Roman domination number of a graph. Applicable Analysis and Discrete Mathematics, 8:155-171, 2014. Google Scholar
  11. T. Bläsius, T. Friedrich, J. Lischeid, K. Meeks, and M. Schirneck. Efficiently enumerating hitting sets of hypergraphs arising in data profiling. Journal of Computer and System Sciences, 124:192-213, 2022. Google Scholar
  12. M. Bonamy, O. Defrain, M. Heinrich, and J.-F. Raymond. Enumerating minimal dominating sets in triangle-free graphs. In R. Niedermeier and C. Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 126 of LIPIcs, pages 16:1-16:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  13. D. Bród. On the number of minimal dominating sets in some classes of trees. Int. J. Contemp. Math. Sciences, 6:503-506, 2011. Google Scholar
  14. K. Casel, H. Fernau, M. Khosravian Ghadikolaei, J. Monnot, and F. Sikora. Extension of some edge graph problems: Standard and parameterized complexity. In L. A. Gasieniec, J. Jansson, and C. Levcopoulos, editors, Fundamentals of Computation Theory - 22nd International Symposium, FCT, volume 11651 of LNCS, pages 185-200. Springer, 2019. Google Scholar
  15. K. Casel, H. Fernau, M. Khosravian Ghadikolaei, J. Monnot, and F. Sikora. Abundant extensions. In T. Calamoneri and F. Corò, editors, Algorithms and Complexity - 12th International Conference, CIAC, volume 12701 of LNCS, pages 3-17. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-75242-2_1.
  16. E. W. Chambers, B. Kinnersley, N. Prince, and D. B. West. Extremal problems for Roman domination. SIAM Journal of Discrete Mathematics, 23:1575-1586, 2009. Google Scholar
  17. M. Chapelle, M. Cochefert, J.-F. Couturier, D. Kratsch, M. Liedloff, and A. Perez. Exact algorithms for weak Roman domination. In T. Lecroq and L. Mouchard, editors, Combinatorial Algorithms - 24th International Workshop, IWOCA, volume 8288 of LNCS, pages 81-93. Springer, 2013. Google Scholar
  18. M. Chellali, T. W. Haynes, S. M. Hedetniemi, S. T. Hedetniemi, and A. A. McRae. A Roman domination chain. Graphs and Combinatorics, 32(1):79-92, 2016. Google Scholar
  19. J.-F. Couturier, P. Heggernes, P. van 't Hof, and D. Kratsch. Minimal dominating sets in graph classes: Combinatorial bounds and enumeration. In M. Bieliková, G. Friedrich, G. Gottlob, S. Katzenbeisser, and G. Turán, editors, SOFSEM 2012: Theory and Practice of Computer Science - 38th Conference on Current Trends in Theory and Practice of Computer Science, volume 7147 of LNCS, pages 202-213. Springer, 2012. Google Scholar
  20. J.-F. Couturier, P. Heggernes, P. van 't Hof, and D. Kratsch. Minimal dominating sets in graph classes: Combinatorial bounds and enumeration. Theoretical Computer Science, 487:82-94, 2013. Google Scholar
  21. J.-F. Couturier, R. Letourneur, and M. Liedloff. On the number of minimal dominating sets on some graph classes. Theoretical Computer Science, 562:634-642, 2015. Google Scholar
  22. N. Creignou, M. Kröll, R. Pichler, S. Skritek, and H. Vollmer. A complexity theory for hard enumeration problems. Discrete Applied Mathematics, 268:191-209, 2019. Google Scholar
  23. P. A. Dreyer. Applications and Variations of Domination in Graphs. PhD thesis, Rutgers University, New Jersey, USA, 2000. Google Scholar
  24. T. Eiter and G. Gottlob. Identifying the minimal transversals of a hypergraph and related problems. SIAM Journal on Computing, 24(6):1278-1304, 1995. Google Scholar
  25. O. Favaron, H. Karami, R. Khoeilar, and S. M. Sheikholeslami. On the Roman domination number of a graph. Discrete Mathematics, 309(10):3447-3451, 2009. Google Scholar
  26. H. Fernau. Roman Domination: a parameterized perspective. International Journal of Computer Mathematics, 85:25-38, 2008. Google Scholar
  27. F. V. Fomin, S. Gaspers, A. V. Pyatkin, and I. Razgon. On the minimum feedback vertex set problem: Exact and enumeration algorithms. Algorithmica, 52(2):293-307, 2008. Google Scholar
  28. F. V. Fomin and D. Kratsch. Exact Exponential Algorithms. Texts in Theoretical Computer Science. Springer, 2010. Google Scholar
  29. A. Gainer-Dewar and P. Vera-Licona. The minimal hitting set generation problem: Algorithms and computation. SIAM Journal of Discrete Mathematics, 31(1):63-100, 2017. Google Scholar
  30. P. A. Golovach, P. Heggernes, M. M. Kanté, D. Kratsch, and Y. Villanger. Enumerating minimal dominating sets in chordal bipartite graphs. Discrete Applied Mathematics, 199:30-36, 2016. Google Scholar
  31. P. A. Golovach, P. Heggernes, M. Moustapha Kanté, D. Kratsch, and Y. Villanger. Minimal dominating sets in interval graphs and trees. Discrete Applied Mathematics, 216:162-170, 2017. Google Scholar
  32. P. A. Golovach, P. Heggernes, and D. Kratsch. Enumerating minimal connected dominating sets in graphs of bounded chordality. Theoretical Computer Science, 630:63-75, 2016. Google Scholar
  33. P. A. Golovach, D. Kratsch, M. Liedloff, and M. Y. Sayadi. Enumeration and maximum number of minimal dominating sets for chordal graphs. Theoretical Computer Science, 783:41-52, 2019. Google Scholar
  34. T. W. Haynes, S.T. Hedetniemi, and M. A. Henning, editors. Topics in Domination in Graphs, volume 64 of Developments in Mathematics. Springer, 2020. Google Scholar
  35. S. T. Hedetniemi, R. R. Rubalcaba, P. J. Slater, and M. Walsh. Few compare to the great Roman empire. Congressus Numerantium, 217:129-136, 2013. Google Scholar
  36. M. M. Kanté, V. Limouzy, A. Mary, and L. Nourine. On the enumeration of minimal dominating sets and related notions. SIAM Journal of Discrete Mathematics, 28(4):1916-1929, 2014. Google Scholar
  37. M. M. Kanté, V. Limouzy, A. Mary, L. Nourine, and T. Uno. Polynomial delay algorithm for listing minimal edge dominating sets in graphs. In F. Dehne, J.-R. Sack, and U. Stege, editors, Workshop on Algorithms and Data Structures, WADS, volume 9214 of LNCS, pages 446-457. Springer, 2015. Google Scholar
  38. M. M. Kanté, V. Limouzy, A. Mary, L. Nourine, and T. Uno. A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs. In E. W. Mayr, editor, International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015, volume 9224 of LNCS, pages 138-153. Springer, 2016. Google Scholar
  39. T. Kraner Šumenjak, P. Pavlić, and A. Tepeh. On the Roman domination in the lexicographic product of graphs. Discrete Applied Mathematics, 160(13-14):2030-2036, 2012. Google Scholar
  40. M. Liedloff. Algorithmes exacts et exponentiels pour les problèmes NP-difficiles: domination, variantes et généralisations. PhD thesis, Université Paul Verlaine - Metz, France, 2007. Google Scholar
  41. M. Liedloff, T. Kloks, J. Liu, and S.-L. Peng. Efficient algorithms for Roman domination on some classes of graphs. Discrete Applied Mathematics, 156(18):3400-3415, 2008. Google Scholar
  42. C.-H. Liu and G. J. Chang. Roman domination on 2-connected graphs. SIAM Journal of Discrete Mathematics, 26(1):193-205, 2012. Google Scholar
  43. C.-H. Liu and G. J. Chang. Upper bounds on Roman domination numbers of graphs. Discrete Mathematics, 312(7):1386-1391, 2012. Google Scholar
  44. C.-H. Liu and G. J. Chang. Roman domination on strongly chordal graphs. Journal of Combinatorial Optimization, 26(3):608-619, 2013. Google Scholar
  45. A. Mary. Énumération des dominants minimaux d'un graphe. PhD thesis, LIMOS, Université Blaise Pascal, Clermont-Ferrand, France, November 2013. Google Scholar
  46. J. L. Mashburn, T. W. Haynes, S. M. Hedetniemi, S. T. Hedetniemi, and P. J. Slater. Differentials in graphs. Utilitas Mathematica, 69:43-54, 2006. Google Scholar
  47. B. P. Mobaraky and S. M. Sheikholeslami. Bounds on Roman domination numbers of graphs. Matematitchki Vesnik, 60:247-253, 2008. Google Scholar
  48. A. Pagourtzis, P. Penna, K. Schlude, K. Steinhöfel, D. S. Taylor, and P. Widmayer. Server placements, Roman domination and other dominating set variants. In R. A. Baeza-Yates, U. Montanari, and N. Santoro, editors, Foundations of Information Technology in the Era of Networking and Mobile Computing, IFIP 17^th World Computer Congress - TC1 Stream / 2^nd IFIP International Conference on Theoretical Computer Science IFIP TCS, pages 280-291. Kluwer, 2002. Also available as Technical Report 365, ETH Zürich, Institute of Theoretical Computer Science, 10/2001. Google Scholar
  49. S.-L. Peng and Y.-H. Tsai. Roman domination on graphs of bounded treewidth. In The 24th Workshop on Combinatorial Mathematics and Computation Theory, pages 128-131, 2007. Google Scholar
  50. G. Rote. The maximum number of minimal dominating sets in a tree. In T. M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1201-1214. SIAM, 2019. Google Scholar
  51. W. Shang, X. Wang, and X. Hu. Roman domination and its variants in unit disk graphs. Discrete Mathematics, Algorithms and Applications, 2(1):99-106, 2010. Google Scholar
  52. Z. Shi and K. M. Koh. Counting the number of minimum Roman dominating functions of a graph. Technical report, ArXiv / CoRR, abs/1403.1019, 2014. URL: https://arxiv.org/abs/1403.1019.
  53. I. B. Skjørten. Faster enumeration of minimal connected dominating sets in split graphs. Master’s thesis, Department of Informatics, University of Bergen, Norway, June 2017. Google Scholar
  54. J. M. M. van Rooij. Exact Exponential-Time Algorithms for Domination Problems in Graphs. PhD thesis, Universiteit Utrecht, The Netherlands, 2011. Google Scholar
  55. H.-M. Xing, X. Chen, and X.-G. Chen. A note on Roman domination in graphs. Discrete Mathematics, 306(24):3338-3340, 2006. Google Scholar
  56. F. Xueliang, Y. Yuansheng, and J. Baoqi. Roman domination in regular graphs. Discrete Mathematics, 309(6):1528-1537, 2009. Google Scholar
  57. I. G. Yero and J. A. Rodríguez-Velázquez. Roman domination in Cartesian product graphs and strong product graphs. Applicable Analysis and Discrete Mathematics, 7:262-274, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact