Twin-distance-hereditary digraphs

DOI10.1016/J.TCS.2023.114009MaRDI QIDQ6132965zbMATH OpenOpenAlexFDO

Authors Dominique Komander, Carolin Rehs

Publication date 21 July 2023

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

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)

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.

Cites work

• scientific article; zbMATH DE number 1420904 (Why is no real title available?)
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
• Acyclic coloring parameterized by directed clique-width
• Classes of directed graphs
• Digraph measures: Kelly decompositions, games, and orderings
• Digraph width measures in parameterized algorithmics
• Digraphs
• Directed NLC-width
• Directed rank-width and displit decomposition
• Distance-hereditary digraphs
• Distance-hereditary graphs
• Forbidden directed minors, directed path-width and directed tree-width of tree-like digraphs
• Fully dynamic recognition algorithm and certificate for directed cographs
• Graph searching games and width measures for directed graphs
• How to compute digraph width measures on directed co-graphs
• Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm
• On the clique-width of some perfect graph classes
• Orientations of digraphs almost preserving diameter
• Rank-width and vertex-minors
• Upper bounds to the clique width of graphs

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)