DAG-width is PSPACE-complete

Saeed Akhoondian Amiri, Stephan Kreutzer, Roman Rabinovich

Berwanger et al. show that for every graph $G$ of size $n$ and DAG-width $k$ there is a DAG decomposition of width $k$ and size $n^{O(k)}$. This gives a polynomial time algorithm f…