2026-07-22T06:50:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15848 2024-03-06T10:56:20Z ddc:004 open_access

Classes of Intersection Digraphs with Good Algorithmic Properties Jaffke, Lars Kwon, O-joung Telle, Jan Arne intersection digraphs H-digraphs reflexive digraphs directed domination directed H-homomorphism 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lars Jaffke and O-joung Kwon and Jan Arne Telle 2022 Is Part Of LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2022.38 urn:nbn:de:0030-drops-158480 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.38 eng https://creativecommons.org/licenses/by/4.0/legalcode