Williams and Nayak were pessimistic about the prospects of generating whole plans quickly even for Burton, i.e., for problem instances with serializable sub-goals and single-effect operators. As our results show, this pessimism was not fully **justified.**
Our work continues the study of planning with unary operators. This apparently easier problem is in fact as hard as the general strips **planning problem (Bylander, 1994). However, we can obtain finer distinctions and some positive results if we pay closer attention to**
the causal structure of the domain. For example, it is easy to **show that when the causal** graph is a tree, it is easy to determine a serializability ordering over any set of sub-goals, and consequently, obtain a plan in polynomial time. In this paper we analyze the relationship between the domain's causal graph and the complexity of **plan generation and plan**
existence. In particular we prove the following results:

- **When the causal graph forms a polytree (the induced undirected graph is acyclic), and**
its node indegree is bounded by a constant, then plan existence and plan generation are polynomial.
- **When the causal graph is directed-path singly connected (there is at most one directed**
path between any pair of nodes), then plan existence is np**-complete.**

- **In general, plan generation for the problems with acyclic causal graphs is provably**
intractable, i.e., the problem requires exponential time. **The corresponding claim** is derived from a previous result by Jonsson and B¨ackstr¨om **(1998b). However, we**
show that the complexity of plan generation for these problems can be bounded by a function of the number of paths within the causal graph.
Note that the complexity of the problems with polytree causal graphs but with unbounded node indegree remains an open problem - it is still to be shown **whether they can be solved**
in polynomial time, or they are np**-complete.**
Finally, we relate our results to an old open question: how difficult is it to generate plans for problems with serializable subgoals **(Korf, 1987)? This question was stated by** Bylander (1992), and different hypotheses were raised by different researchers. Here, we present a clear, though somewhat disappointing answer: First, our results suggest that even when the underlying causal graph of the problem is acyclic (and thus the problem is known to be serializable), finding a serialization ordering on the **problem subgoals may be hard.** Second, we show that even if the actual serialization ordering on the subgoals is known, solving the problem is not necessarily easy.

The rest of this paper is organized as follows: In Section 2 we **first introduce some**
basic formalism used in the paper, then discuss, motivate and illustrate the notion of causal graph. In Sections 3 and 4 we present our results on the relation between the form of the causal graph and the complexity of the planning problem. **In Section 5 we discuss the** sub-goal serializability issue and the impact of our results on it. In Section 6 we describe some related work on complexity of planning, and connect our **work with the previous** results. We summarize in Section 7. Finally, Appendix A provides a short review of the POP algorithm (Penberthy & Weld, 1992), and Appendix B provides some of the proofs.