Characterizations and directed path-width of sequence digraphs

DOI10.1007/S00224-022-10104-WMaRDI QIDQ6038712zbMATH OpenOpenAlexFDO

Authors Frank Gurski, Carolin Rehs, Jochen Rethmann

Publication date 2 May 2023

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

digraphsdirected path-widthtransitive tournamentsXP-algorithm

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Dynamic programming (90C39)

Abstract: Computing the directed path-width of a directed graph is an NP-hard problem. Even for digraphs of maximum semi-degree 3 the problem remains hard. We propose a decomposition of an input digraph G=(V,A) by a number k of sequences with entries from V, such that (u,v) in A if and only if in one of the sequences there is an occurrence of u appearing before an occurrence of v. We present several graph theoretical properties of these digraphs. Among these we give forbidden subdigraphs of digraphs which can be defined by k=1 sequence, which is a subclass of semicomplete digraphs. Given the decomposition of digraph G, we show an algorithm which computes the directed path-width of G in time O(kcdot (1+N)^k), where N denotes the maximum sequence length. This leads to an XP-algorithm w.r.t. k for the directed path-width problem. Our result improves the algorithms of Kitsunai et al. for digraphs of large directed path-width which can be decomposed by a small number of sequence.

Recommendations

• Directed path-width of sequence digraphs
• Computing Directed Pathwidth in O(1.89 n ) Time
• Computing directed pathwidth in O(1.89ⁿ) time
• A Polynomial Time Algorithm for Bounded Directed Pathwidth
• Directed path-width and directed tree-width of directed co-graphs

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A note on exact algorithms for vertex ordering problems on graphs
• A partial k-arboretum of graphs with bounded treewidth
• Complexity of Finding Embeddings in a k-Tree
• Computing directed pathwidth in O(1.89ⁿ) time
• Computing the pathwidth of directed graphs with small vertex cover
• Digraph searching, directed vertex separation and directed pathwidth
• Digraphs
• Directed path-width and monotonicity in digraph searching
• Directed path-width of sequence digraphs
• Directed tree-width
• Graph minors. I. Excluding a forest
• scientific article; zbMATH DE number 6271443 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• Linear layouts in submodular systems
• Min Cut is NP-complete for edge weighted trees
• On the complexity of the FIFO stack-up problem
• On the pathwidth of almost semicomplete digraphs
• On the pathwidth of chordal graphs
• Tournament immersion and cutwidth
• Word-Representable Graphs: a Survey

Cited in

(6)

• Directed path-width of sequence digraphs
• A slice theoretic approach for embedding problems on digraphs
• Computing directed pathwidth in O(1.89ⁿ) time
• On the pathwidth of almost semicomplete digraphs
• Directed path-decompositions
• scientific article; zbMATH DE number 7650942 (Why is no real title available?)

This page was built for publication: Characterizations and directed path-width of sequence digraphs

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