Back to Search Start Over

Classes of intersection digraphs with good algorithmic properties.

Authors :
Jaffke, Lars
Kwon, O‐joung
Telle, Jan Arne
Source :
Journal of Graph Theory. May2024, Vol. 106 Issue 1, p110-148. 39p.
Publication Year :
2024

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 $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. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
03649024
Volume :
106
Issue :
1
Database :
Academic Search Index
Journal :
Journal of Graph Theory
Publication Type :
Academic Journal
Accession number :
176118804
Full Text :
https://doi.org/10.1002/jgt.23065