Twin-distance-hereditary digraphs

DOI10.1016/J.TCS.2023.114009arXiv2112.04183OpenAlexW4379741177MaRDI QIDQ6132965FDOQ6132965

Dominique Komander, Carolin Rehs

Publication date: 21 July 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: We investigate structural and algorithmic advantages of a directed version of the well-researched class of distance-hereditary graphs. Since the previously defined distance-hereditary digraphs do not permit a recursive structure, we define directed twin-distance-hereditary graphs, which can be constructed by several twin and pendant vertex operations analogously to undirected distance-hereditary graphs and which still preserves the distance hereditary property. We give a characterization by forbidden induced subdigraphs and place the class in the hierarchy, comparing it to related classes. We further show algorithmic advantages concerning directed width parameters, directed graph coloring and some other well-known digraph problems which are NP-hard in general, but computable in polynomial or even linear time on twin-distance-hereditary digraphs. This includes computability of directed path-width and tree-width in linear time and the directed chromatic number in polynomial time. From our result that directed twin-distance-hereditary graphs have directed clique-width at most $3$ it follows by Courcelle's theorem on directed clique-width that we can compute every graph problem describable in which is describable in monadic second-order logic on quantification over vertices and vertex sets as well as some further problems like Hamiltonian Path/Cycle in polynomial time.

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

zbMATH Keywords

directed clique-widthdirected distance-hereditary graphsdirected width parameters

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Upper bounds to the clique width of graphs
• Digraph width measures in parameterized algorithmics
• Title not available (Why is that?)
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• Digraphs
• Digraph measures: Kelly decompositions, games, and orderings
• Distance-hereditary graphs
• Rank-width and vertex-minors
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• Fully dynamic recognition algorithm and certificate for directed cographs
• How to compute digraph width measures on directed co-graphs
• Forbidden directed minors, directed path-width and directed tree-width of tree-like digraphs
• Directed NLC-width
• Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm
• Title not available (Why is that?)
• A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
• Orientations of digraphs almost preserving diameter
• Classes of Directed Graphs
• Acyclic coloring parameterized by directed clique-width
• Directed Rank-Width and Displit Decomposition
• Distance-hereditary digraphs

Cited In (1)

• Double-crossed chords and distance-hereditary graphs

This page was built for publication: Twin-distance-hereditary digraphs

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