able with respect to every variable it affects. An operator A is irreplaceable **with respect**
to a variable v if the removal of all edges from Gv that stem from A **disconnects some**
weakly connected component of Gv. (2) For every variable v, the graph Gv**, restricted to**
the set of values that appear in the prevail conditions of some operators, is acyclic. (3) Any sequence of operators annotating a path from x to y in the domain transition graph of v**, is**
stronger than all shortest such sequences connecting x and y. Here, a sequence A1**, . . . , A**k is stronger **than** A′1
, . . . , A′l if there is a subsequence Ai1
, . . . , Ail of A1, . . . , Ak **such that for**
every 1 ≤ j ≤ l**, the prevail conditions of** A′j are a subset of the prevail conditions of Aij
.

Jonsson and B¨ackstr¨om present a map of the computational complexity of problems with different restrictions, displaying the frontier between the tractable and intractable cases.

Each domain transition graph combines and structures the influence of many operators on a particular variable. Therefore, they provide us a more global picture than the operator set alone. Hence, in spite of the fact that domain transition **graphs do not capture the relationship between different variables, they do allow us to express some structural properties**
that address interactions between the variables (e.g., see **property (2) above).**
Observe that domain transition graphs are not very informative in the case of propositional planning, since they are only distinguish between the variables that can be changed only in one direction and the variables that can be changed in **both directions. Although** this property of domain transition graphs allows to distinguish between the polynomial planning with only positive postconditions, and the pspace**-complete planning with both**
positive and negative postconditions (Bylander, 1994), it **seems to be not very helpful in**
further hierarchical refinement of the propositional planning complexity. On the other hand, there is no a priori reason why the causal graphs will not be informative in the multi-valued case. Exploiting the properties of causal graphs, together **with the properties of domain**
transition graphs, seems to be a natural direction to extend **the work presented in this paper.** The recent work of Domshlak and Dinitz (2001) on multi-entity off-line coordination can be seen as investigating connections between the structure of **the causal graph, together with** the properties of the domain transition graphs, and the complexity of the corresponding problems in case of multi-valued domains. To the best of our knowledge, this is the only work that was done with respect to such a "mixed" structural analysis, and a lot of work remains to be done. For instance, combining various properties of the domain transition graphs studied by Jonsson and B¨ackstr¨om (1998a), with the **properties of the problem's** causal graph is a direction for the further research.

## 7. Summary And Future Work

We have shown that the form of the causal graph for strips **planning problems with unary**
operators is an important factor in determining the computational complexity of plan generation. In particular, we have shown that a polynomial time **algorithm exists for any**
problem with a polytree causal graph and the node indegree bounded by a constant. More generally, this result shows that planning with polytree causal graphs is at most (what is often referred to in the Bayes nets literature as) locally exponential, i.e., it is exponential in the maximal number of parents of a node. Note that in hardware-control planning problems the maximal node indegree is expected to be small, since prevail dependencies between the variables reflect the direct interconnections between the corresponding hard-