Directed Path-Decompositions

Joshua Erde*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


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 ≥ k contains each arboresence of order ≤ k+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.

Original languageEnglish
Pages (from-to)415-430
Number of pages16
JournalSIAM Journal on Discrete Mathematics
Issue number1
Publication statusPublished - 1 Jan 2020


  • Linked tree-decomposition
  • Path-width
  • Tree-decomposition

ASJC Scopus subject areas

  • Mathematics(all)


Dive into the research topics of 'Directed Path-Decompositions'. Together they form a unique fingerprint.

Cite this