DAG-width is PSPACE-complete

DOI10.1016/j.tcs.2016.09.011zbMath1353.68105arXiv1411.2438OpenAlexW2964025853MaRDI QIDQ343929

Stephan Kreutzer, Saeed Akhoondian Amiri, Roman Rabinovich

Publication date: 29 November 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

PSPACE-completegraph searching gamesDAG-width

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Directed width parameters on semicomplete digraphs, Congestion-Free Rerouting of Flows on DAGs, How to compute digraph width measures on directed co-graphs, Forbidden directed minors and Kelly-width

Cites Work

• Unnamed Item
• Unnamed Item
• The dag-width of directed graphs
• Digraph measures: Kelly decompositions, games, and orderings
• On the domination search number
• Directed tree-width
• Directed path-width and monotonicity in digraph searching
• Approximation Algorithms for Domination Search
• Mathematical Foundations of Computer Science 2005
• Distance d-Domination Games