Solving planning domains with polytree causal graphs is NP-complete
<|reference_start|>Solving planning domains with polytree causal graphs is NP-complete: We show that solving planning domains on binary variables with polytree causal graph is \NP-complete. This is in contrast to a polynomial-time algorithm of Domshlak and Brafman that solves these planning domains for polytree causal graphs of bounded indegree.<|reference_end|>
@article{giménez2006solving,
    title={Solving planning domains with polytree causal graphs is NP-complete},
    author={Omer Gim'enez},
    journal={arXiv preprint arXiv:cs/0610095},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0610095},
    primaryClass={cs.AI cs.CC}
}