Classes of intersection digraphs with good algorithmic properties

DOI10.1002/JGT.23065MaRDI QIDQ6201028zbMATH OpenFDO

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

Publication date 25 March 2024

Published in Journal of Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2105.01413

zbMATH Keywords

intersection digraphsdirected dominationreflexive digraphs\(H\)-digraphsdirected \(H\)-homomorphism

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76)

Abstract: An intersection digraph is a digraph where every vertex $v$ is represented by an ordered pair $(S_v,T_v)$ of sets such that there is an edge from $v$ to $w$ if and only if $S_v$ and $T_w$ intersect. An intersection digraph is reflexive if $S_{v}cap{T}_{v}eqemptyset$ for every vertex $v$. Compared to well-known undirected intersection graphs like interval graphs and permutation graphs, not many algorithmic applications on intersection digraphs have been developed. Motivated by the successful story on algorithmic applications of intersection graphs using a graph width parameter called mim-width, we introduce its directed analogue called `bi-mim-width' and prove that various classes of reflexive intersection digraphs have bounded bi-mim-width. In particular, we show that as a natural extension of $H$-graphs, reflexive $H$-digraphs have linear bi-mim-width at most $12|E(H)|$, which extends a bound on the linear mim-width of $H$-graphs [On the Tractability of Optimization Problems on $H$-Graphs. Algorithmica 2020]. For applications, we introduce a novel framework of directed versions of locally checkable problems, that streamlines the definitions and the study of many problems in the literature and facilitates their common algorithmic treatment. We obtain unified polynomial-time algorithms for these problems on digraphs of bounded bi-mim-width, when a branch decomposition is given. Locally checkable problems include Kernel, Dominating Set, and Directed $H$-Homomorphism.

Recommendations

• Digraph width measures in parameterized algorithmics
• On digraph width measures in parameterized algorithmics
• Directed nowhere dense classes of graphs
• Mim-width. I. Induced path problems
• Are there any good digraph width measures?

Cites work

• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 2191983 (Why is no real title available?)
• scientific article; zbMATH DE number 3106184 (Why is no real title available?)
• A new generalization of kernels in digraphs
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Algorithms for interval catch digraphs
• Bipartite spanning sub(di)graphs induced by 2-partitions
• Circular‐arc digraphs: A characterization
• Classes of directed graphs
• Connection digraphs and second-order line digraphs
• Degree constrained 2-partitions of semicomplete digraphs
• Directed tree-width
• Dominating Set and Converse Dominating Set of a Directed Graph
• Efficient domination of the orientations of a graph
• Efficient total domination in digraphs
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Finding good 2-partitions of digraphs. II. Enumerable properties
• Graph Classes: A Survey
• Graph classes with structured neighborhoods and algorithmic applications
• Graph minors. X: Obstructions to tree-decomposition
• Graph theory
• Homomorphisms and colourings of oriented graphs: an updated survey
• Independent domination in directed graphs
• Interval digraphs: An analogue of interval graphs
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• Linear MIM-width of trees
• Lower bounds on the mim-width of some graph classes
• Maximum \(k\)-regular induced subgraphs
• Mim-width. III. Graph powers and generalized distance domination problems
• On the \(k\)-domination number of digraphs
• On the kernel and related problems in interval digraphs
• On the tractability of optimization problems on \(H\)-graphs
• Out-colourings of digraphs
• Out-degree reducing partitions of digraphs
• Precoloring extension. I: Interval graphs
• Rank-width and vertex-minors
• Rank‐width is less than or equal to branch‐width
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Solving problems on generalized convex graphs via mim-width
• The chromatic number of oriented graphs
• The directed grid theorem
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• The rank-width of edge-coloured graphs
• The simple chromatic number of oriented graphs
• Total and connected domination in digraphs

This page was built for publication: Classes of intersection digraphs with good algorithmic properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6201028)