# A Structural Complexity Analysis of Hierarchical Task Network Planning

arXiv: https://arxiv.org/abs/2401.14174 · HTML: https://mlsanity.com/paper/2401.14174/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 59 references that are in the map.
- First posted on arXiv 25 Jan 2024.

## Builds on (most cited first, 7 of 7)

- [Non-Clashing Teaching Maps for Balls in Graphs](https://mlsanity.com/paper/2309.02876/) (2023)
- [Modification-Fair Cluster Editing](https://mlsanity.com/paper/2112.03183/) (2021)
- [A Complete Parameterized Complexity Analysis of Bounded Planning](https://mlsanity.com/paper/1310.7828/) (2013)
- [Hollow Heaps](https://mlsanity.com/paper/1510.06535/) (2015)
- [Precedence-constrained scheduling problems parameterized by partial order width](https://mlsanity.com/paper/1605.00901/) (2016)
- [Equitable Scheduling on a Single Machine](https://mlsanity.com/paper/2010.04643/) (2020)
- [Bounding and computing obstacle numbers of graphs](https://mlsanity.com/paper/2206.15414/) (2022)

## Abstract (arXiv)

We perform a refined complexity-theoretic analysis of three classical problems in the context of Hierarchical Task Network Planning: the verification of a provided plan, whether an executable plan exists, and whether a given state can be reached. Our focus lies on identifying structural properties which yield tractability. We obtain new polynomial algorithms for all three problems on a natural class of primitive networks, along with corresponding lower bounds. We also obtain an algorithmic meta-theorem for lifting polynomial-time solvability from primitive to general task networks, and prove that its preconditions are tight. Finally, we analyze the parameterized complexity of the three problems.