ware components. Likewise we have shown that for a problem with directed-path singly connected causal graph the maximal plan length is a low order **polynomial, but the problem**
is np-complete. More generally, we have shown a relation between **the number of paths between variables in the causal graph and the computational complexity of the corresponding**
planning problem. Finally we have presented the impact of our results on the question of complexity of planning problems with serializable subgoals, and connected our work with previous results on planning complexity.

Our work leaves a number of open questions with respect to purely syntactical, and a mixture of both structural and syntactical restrictions on **the planning problems with unary** operators. In the former case, one of the most important directions is a further analysis of causal graphs with constantly bounded node indegree. It turns out that complexity analysis for this class of problems will be very helpful in understanding various computational properties of CP-nets (Boutilier et al., 1999). Although here we provided a partial answer for this question, the general picture of the worst-case complexity for this class of problems is not clear. For example, if the indegree of the causal graph **is known to be bounded by**
2, and this is the only structural property of the causal graph, it is even not clear whether this problem subclass is in np.

In the latter case, various syntactical restrictions can be **analysed together with the form**
of the causal graph. For example, one may be interested in the **computational properties** of the problems with acyclic causal graphs, and the restriction that every operator has at most α prevail conditions, where α **is bounded by a constant. This, as well as many other**
related questions with respect to various special cases of planning with unary operators are of interest for the future work.

## Acknowledgments

A preliminary version of this paper appeared in the Sixth International Conference on Artificial Intelligence Planning and Scheduling, April, 2002. We would like to thank the three anonymous reviewers for their extremely helpful comments. **Ronen Brafman is supported**
in part by the Paul Ivanier Center for Robotics Research and Production Management.