Document Open Access Logo

Classes of Intersection Digraphs with Good Algorithmic Properties

Authors Lars Jaffke , O-joung Kwon , Jan Arne Telle

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.38.pdf
  • Filesize: 0.9 MB
  • 18 pages

Document Identifiers

Author Details

Lars Jaffke
  • Department of Informatics, University of Bergen, Norway
O-joung Kwon
  • Department of Mathematics, Incheon National University, South Korea
  • Institute for Basic Science, South Korea
Jan Arne Telle
  • Department of Informatics, University of Bergen, Norway

Funding

  • Jaffke, Lars: Supported by the Norwegian Research Council via project 274526.
  • Kwon, O-joung: Supported by the National Research Foundation of Korea (NRF) grant funded by the Ministry of Education (No. NRF-2018R1D1A1B07050294) and by Institute for Basic Science (IBS-R029-C1).

Cite AsGet BibTex

Lars Jaffke, O-joung Kwon, and Jan Arne Telle. Classes of Intersection Digraphs with Good Algorithmic Properties. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 38:1-38:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.STACS.2022.38

Abstract

While intersection graphs play a central role in the algorithmic analysis of hard problems on undirected graphs, the role of intersection digraphs in algorithms is much less understood. We present several contributions towards a better understanding of the algorithmic treatment of intersection digraphs. First, we introduce natural classes of intersection digraphs that generalize several classes studied in the literature. Second, we define the directed locally checkable vertex (DLCV) problems, which capture many well-studied problems on digraphs such as (Independent) Dominating Set, Kernel, and H-Homomorphism. Third, we give a new width measure of digraphs, bi-mim-width, and show that the DLCV problems are polynomial-time solvable when we are provided a decomposition of small bi-mim-width. Fourth, we show that several classes of intersection digraphs have bounded bi-mim-width, implying that we can solve all DLCV problems on these classes in polynomial time given an intersection representation of the input digraph. We identify reflexivity as a useful condition to obtain intersection digraph classes of bounded bi-mim-width, and therefore to obtain positive algorithmic results.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • intersection digraphs
  • H-digraphs
  • reflexive digraphs
  • directed domination
  • directed H-homomorphism

Metrics

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

Related Versions

References

  1. Noga Alon, Jørgen Bang-Jensen, and Stéphane Bessy. Out-colourings of digraphs. J. Graph Theory, 93(1):88-112, 2020. URL: https://doi.org/10.1002/jgt.22476.
  2. S. Arumugam, K. Jacob, and Lutz Volkmann. Total and connected domination in digraphs. Australas. J Comb., 39:283-292, 2007. URL: http://ajc.maths.uq.edu.au/pdf/39/ajc_v39_p283.pdf.
  3. Jørgen Bang-Jensen, Stéphane Bessy, Frédéric Havet, and Anders Yeo. Out-degree reducing partitions of digraphs. Theor. Comput. Sci., 719:64-72, 2018. URL: https://doi.org/10.1016/j.tcs.2017.11.007.
  4. Jørgen Bang-Jensen, Stéphane Bessy, Frédéric Havet, and Anders Yeo. Bipartite spanning sub(di)graphs induced by 2-partitions. J. Graph Theory, 92(2):130-151, 2019. URL: https://doi.org/10.1002/jgt.22444.
  5. Jørgen Bang-Jensen and Tilde My Christiansen. Degree constrained 2-partitions of semicomplete digraphs. Theor. Comput. Sci., 746:112-123, 2018. URL: https://doi.org/10.1016/j.tcs.2018.06.028.
  6. Jørgen Bang-Jensen, Nathann Cohen, and Frédéric Havet. Finding good 2-partitions of digraphs II. Enumerable properties. Theor. Comput. Sci., 640:1-19, 2016. URL: https://doi.org/10.1016/j.tcs.2016.05.034.
  7. Jørgen Bang-Jensen and Gregory Gutin, editors. Classes of directed graphs. Springer Monographs in Mathematics. Springer, Cham, 2018. URL: https://doi.org/10.1007/978-3-319-71840-8.
  8. David W. Bange, Anthony E. Barkauskas, Linda H. Host, and Lane H. Clark. Efficient domination of the orientations of a graph. Discret. Math., 178(1-3):1-14, 1998. URL: https://doi.org/10.1016/S0012-365X(97)81813-4.
  9. Lowell W. Beineke and Christina M. Zamfirescu. Connection digraphs and second-order line digraphs. Discrete Math., 39(3):237-254, 1982. URL: https://doi.org/10.1016/0012-365X(82)90147-9.
  10. Rémy Belmonte and Martin Vatshelle. Graph classes with structured neighborhoods and algorithmic applications. Theor. Comput. Sci., 511:54-65, 2013. URL: https://doi.org/10.1016/j.tcs.2013.01.011.
  11. Miklós Biró, Mihály Hujter, and Zsolt Tuza. Precoloring extension. I. Interval graphs. Discret. Math., 100(1-3):267-279, 1992. URL: https://doi.org/10.1016/0012-365X(92)90646-W.
  12. Flavia Bonomo-Braberman, Nick Brettell, Andrea Munaro, and Daniël Paulusma. Solving problems on generalized convex graphs via mim-width. In Anna Lubiw and Mohammad R. Salavatipour, editors, Proceedings of the 17th International Symposium on Algorithms and Data Structures (WADS 2021), volume 12808 of Lecture Notes in Computer Science, pages 200-214. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-83508-8_15.
  13. Andreas Brandstädt, Van Bang Le, and Jeremy P. Spinrad. Graph classes: a survey. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. URL: https://doi.org/10.1137/1.9780898719796.
  14. Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle. Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theor. Comput. Sci., 511:66-76, 2013. Google Scholar
  15. Domingos Moreira Cardoso, Marcin Kaminski, and Vadim V. Lozin. Maximum k-regular induced subgraphs. J. Comb. Optim., 14(4):455-463, 2007. URL: https://doi.org/10.1007/s10878-007-9045-9.
  16. Michael Cary, Jonathan Cary, and Savari Prabhu. Independent domination in directed graphs. Communications in Combinatorics and Optimization, 6(1):67-80, 2021. URL: https://doi.org/10.22049/cco.2020.26845.1149.
  17. Gary Chartrand, Peter Dankelmann, Michelle Schultz, and Henda C. Swart. Twin domination in digraphs. Ars Comb., 67, 2003. Google Scholar
  18. Bruno Courcelle. The monadic second order logic of graphs VI: on several representations of graphs by relational structures. Discret. Appl. Math., 54(2-3):117-149, 1994. URL: https://doi.org/10.1016/0166-218X(94)90019-1.
  19. Reinhard Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer, Heidelberg, fourth edition, 2010. URL: https://doi.org/10.1007/978-3-642-14279-6.
  20. Tomás Feder, Pavol Hell, Jing Huang, and Arash Rafiey. Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms. Discrete Appl. Math., 160(6):697-707, 2012. URL: https://doi.org/10.1016/j.dam.2011.04.016.
  21. Fedor V. Fomin, Petr A. Golovach, and Jean-Florent Raymond. On the tractability of optimization problems on H-graphs. Algorithmica, 82(9):2432-2473, 2020. URL: https://doi.org/10.1007/s00453-020-00692-9.
  22. Mathew C. Francis, Pavol Hell, and Dalu Jacob. On the kernel and related problems in interval digraphs. In Hee-Kap Ahn and Kunihiko Sadakane, editors, Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC 2021), volume 212 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1-17:17, Dagstuhl, Germany, 2021. Schloss Dagstuhl. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2021.17.
  23. Yumin Fu. Dominating set and converse dominating set of a directed graph. The American Mathematical Monthly, 75(8):861-863, 1968. URL: http://www.jstor.org/stable/2314337.
  24. J. Ghoshal, Renu Laskar, and D. Pillone. Topics on domination in directed graphs. In Theresa W. Haynes, Stephen T. Hedetniemi, and Peter J. Slater, editors, Domination in Graphs: Advanced Topics. Taylor & Francis, 2017. Google Scholar
  25. Pavol Hell and Jaroslav Nesetril. Graphs and homomorphisms, volume 28 of Oxford lecture series in mathematics and its applications. Oxford University Press, 2004. Google Scholar
  26. Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle. Mim-width III. Graph powers and generalized distance domination problems. Theoret. Comput. Sci., 796:216-236, 2019. URL: https://doi.org/10.1016/j.tcs.2019.09.012.
  27. Thor Johnson, Neil Robertson, P. D. Seymour, and Robin Thomas. Directed tree-width. J. Combin. Theory Ser. B, 82(1):138-154, 2001. URL: https://doi.org/10.1006/jctb.2000.2031.
  28. Dong Yeap Kang, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle. A width parameter useful for chordal and co-comparability graphs. Theoret. Comput. Sci., 704:1-17, 2017. URL: https://doi.org/10.1016/j.tcs.2017.09.006.
  29. Mamadou Moustapha Kanté. The rank-width of directed graphs. preprint, 2007. URL: http://arxiv.org/abs/0709.1433.
  30. Mamadou Moustapha Kanté and Michael Rao. The rank-width of edge-coloured graphs. Theory Comput. Syst., 52(4):599-644, 2013. URL: https://doi.org/10.1007/s00224-012-9399-y.
  31. Stephan Kreutzer and O-joung Kwon. Digraphs of bounded width. In Jørgen Bang-Jensen and Gregory Z. Gutin, editors, Classes of Directed Graphs, Springer Monographs in Mathematics, pages 405-466. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-71840-8_9.
  32. Stefan Mengel. Lower bounds on the mim-width of some graph classes. Discrete Appl. Math., 248:28-32, 2018. URL: https://doi.org/10.1016/j.dam.2017.04.043.
  33. Haiko Müller. Recognizing interval digraphs and interval bigraphs in polynomial time. Discrete Appl. Math., 78(1-3):189-205, 1997. URL: https://doi.org/10.1016/S0166-218X(97)00027-9.
  34. Lyes Ouldrabah, Mostafa Blidia, and Ahmed Bouchou. On the k-domination number of digraphs. J. Comb. Optim., 38(3):680-688, 2019. URL: https://doi.org/10.1007/s10878-019-00405-1.
  35. Erich Prisner. Algorithms for interval catch digraphs. Discret. Appl. Math., 51(1-2):147-157, 1994. URL: https://doi.org/10.1016/0166-218X(94)90104-X.
  36. Amina Ramoul and Mostafa Blidia. A new generalization of kernels in digraphs. Discret. Appl. Math., 217:673-684, 2017. URL: https://doi.org/10.1016/j.dam.2016.09.048.
  37. Oliver Schaudt. Efficient total domination in digraphs. J. Discrete Algorithms, 15:32-42, 2012. URL: https://doi.org/10.1016/j.jda.2012.02.003.
  38. M. Sen, S. Das, A. B. Roy, and D. B. West. Interval digraphs: an analogue of interval graphs. J. Graph Theory, 13(2):189-202, 1989. URL: https://doi.org/10.1002/jgt.3190130206.
  39. M. Sen, S. Das, and Douglas B. West. Circular-arc digraphs: a characterization. J. Graph Theory, 13(5):581-592, 1989. URL: https://doi.org/10.1002/jgt.3190130508.
  40. Petra Smolíková. The simple chromatic number of oriented graphs. Electronic Notes in Discrete Mathematics, 5:281-283, 2000. URL: https://doi.org/10.1016/S1571-0653(05)80186-6.
  41. Eric Sopena. The chromatic number of oriented graphs. J. Graph Theory, 25(3):191-205, 1997. URL: https://doi.org/10.1002/(SICI)1097-0118(199707)25:3<191::AID-JGT3>3.0.CO;2-G.
  42. Éric Sopena. Homomorphisms and colourings of oriented graphs: An updated survey. Discret. Math., 339(7):1993-2005, 2016. URL: https://doi.org/10.1016/j.disc.2015.03.018.
  43. Jan Arne Telle and Andrzej Proskurowski. Algorithms for vertex partitioning problems on partial k-trees. SIAM J. Discrete Math., 10(4):529-550, 1997. URL: https://doi.org/10.1137/S0895480194275825.
  44. Martin Vatshelle. New Width Parameters of Graphs. PhD thesis, Univ. Bergen, 2012. Google Scholar
  45. John von Neumann and Oskar Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, Princeton, New Jersey, 1944. 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 Imprint Privacy Contact