Directed path-decompositions

DOI10.1137/19M1248728MaRDI QIDQ5215903zbMATH OpenOpenAlexFDO

Authors Joshua Erde

Publication date 13 February 2020

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

tree-decompositionpath-widthlinked tree-decomposition

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83)

Abstract: Many of the tools developed for the theory of tree-decompositions of graphs do not work for directed graphs. In this paper we show that some of the most basic tools do work in the case where the model digraph is a directed path. Using these tools we define a notion of a directed blockage in a digraph and prove a min-max theorem for directed path-width analogous to the result of Bienstock, Roberston, Seymour and Thomas for blockages in graphs. Furthermore, we show that every digraph with directed path width $geqk$ contains each arboresence of order $leqk+1$ as a butterfly minor. Finally we also show that every digraph admits a linked directed path-decomposition of minimum width, extending a result of Kim and Seymour on semi-complete digraphs.

Recommendations

• Forbidden directed minors, directed path-width and directed tree-width of tree-like digraphs
• Towards the graph minor theorems for directed graphs
• Directed path-width and directed tree-width of directed co-graphs
• Digraphs of bounded width
• Characterizations and directed path-width of sequence digraphs

Cites work

• scientific article; zbMATH DE number 1870231 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• A Menger-like property of tree-width: The finite case
• A unified treatment of linked and lean tree-decompositions
• An algorithmic metatheorem for directed treewidth
• DAG-width
• Digraph measures: Kelly decompositions, games, and orderings
• Digraphs of bounded width
• Directed path-width and monotonicity in digraph searching
• Directed tree-width
• Graph Minors I: A Short Proof of the Path-width Theorem
• Graph minors. X: Obstructions to tree-decomposition
• Graph searching and a min-max theorem for tree-width
• Introducing directed tree width
• Mathematical Foundations of Computer Science 2005
• Parameters tied to treewidth
• Quickly excluding a forest
• Submodular partition functions
• Tangle-tree duality: in graphs, matroids and beyond
• The dag-width of directed graphs
• The directed grid theorem
• Tournament minors
• Unifying duality theorems for width parameters in graphs and matroids (extended abstract)

Cited in

(7)

• Assur decompositions of direction-length frameworks
• Digraphs of directed treewidth one
• Tangle-tree duality in abstract separation systems
• Topological Decomposition of Directed Graphs
• Forbidden directed minors, directed path-width and directed tree-width of tree-like digraphs
• scientific article; zbMATH DE number 4183442 (Why is no real title available?)
• Paths algebra, similarities and system decomposition

This page was built for publication: Directed path-decompositions

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