DAG-width is PSPACE-complete.

Saeed Akhoondian Amiri Stephan Kreutzer Roman Rabinovich

Published in: Theor. Comput. Sci. (2016)

Keyphrases

pspace complete
np complete
model checking
satisfiability problem
decision problems
directed acyclic graph
exptime complete
strips planning
tree automata
phase transition
computational complexity
causal graph
np hard
probability distribution
constraint satisfaction problems
random variables