Directed path-decompositions

DOI10.1137/19M1248728zbMATH Open1432.05079arXiv1711.00718OpenAlexW3006501763MaRDI QIDQ5215903FDOQ5215903

Authors: Joshua Erde 

Publication date: 13 February 2020

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

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.

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

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

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)

Cites Work

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

Cited In (7)

• Tangle-tree duality in abstract separation systems
• Digraphs of directed treewidth one
• Topological Decomposition of Directed Graphs
• Forbidden directed minors, directed path-width and directed tree-width of tree-like digraphs
• Title not available (Why is that?)
• Assur decompositions of direction-length frameworks
• 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)