Classes of intersection digraphs with good algorithmic properties

DOI10.1002/JGT.23065arXiv2105.01413MaRDI QIDQ6201028FDOQ6201028

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)

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.

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

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?

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)

Cites Work

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