that the maximal indegree of such a polytree can be minimal, i.e. equal to 2. Thus, the proposition is valid for any polytree that is not a tree. 

From Proposition 3 it follows that Theorems 1 and 4 introduce **new polynomial and**
np**-easy subclasses of the UB problem class, respectively.**

## 6.3 Structural Restrictions In Propositional Planning

Jonsson and B¨ackstr¨om (1998b) present the 3S class of planning problems. This class is most closely related to the problems examined in this paper, since it defines a special subclass of problems with binary variables, unary operators and acyclic causal graphs. The 3S problem class is defined by posing some additional, relatively severe, restrictions on the problem's operator set: Each variable v in a 3S problem instance is required to be either (i) **static**,
i.e., unchangeable; (ii) symmetrically reversible, i.e., for each operator A affecting v**, there**
exist an operator A′ affecting v **with the same prevail conditions and the opposite effect;**
or (iii) splitting. For the formal definition of the splitting property we refer **to Jonsson**
and B¨ackstr¨om (1998b). Informally, if a binary variable v **is splitting then the problem**
instance can be split into three, well-defined subproblems that can be solved independently.

For this class of planning problems it was shown that plan existence can be determined in polynomial time, while plan generation is provably intractable, since there are instances of 3S with exponentially long minimal solutions. In particular, the problem instance that we used in the proof of Theorem 3 is in 3S.

The complexity analysis by Jnonsson and B¨ackstr¨om (1998b) is somewhat unique in the research on complexity of propositional planning, since, to the best of our knowledge, this was the only attempt to exploit not only syntactical restrictions on the operator set, but also some structural restrictions on interaction between the variables. Our analysis can be seen as continuing this direction by looking on the structural restrictions only**. We**
believe that eliminating the marginal effect of the problem structure on the problem's (potential) hardness will allow us to understand better the connection between the component interactions topology, and the potential complexity of the **problem.**

## 6.4 Structural Restrictions In Multi-Valued Formalisms

When the variables are no longer propositional, some additional properties of the problems can be identified, and, possibly, exploited. In particular, **additional internal structures of** the problem can be analysed.

Jonsson and B¨ackstr¨om (1998a) analyze different properties of a multi-valued problem structure, which is called the domain transition graph**. Such a structure is defined for each**
state variable of the problem, and it describes possible transitions between different values of this variable. The domain transition graph of a state variable v **is a directed labeled**
graph Gv = (V, E), where V is associated with the v's set of possible values, D(v**), and**
(x, A, y) ∈ E if and only if the operator A can be applied at some state in which v = x**, and**
its application results in a state in which v = y **holds.**
Jonsson and B¨ackstr¨om identify sets of structural restrictions on domain transition graphs which make planning instances tractable. Roughly, the properties are the following: (1) The problem domain is interference-safe, i.e., each operator is either unary or irreplace-