Proof: Consider a UB problem with a tree causal graph, and suppose that it is not postunique. It means that there exist a variable v ∈ V, with D(v) = {v
′, v′′}**, such that there**
exist two operators A1, A2 ∈ Λv that change the value of v **from** v
′to v
′′**, and** prv(A1) 6=
prv(A2).

From the assumption that the causal graph forms a tree it follows that |pred(v)| ≤ 1.

If pred(v) = ∅**, then it is easy to see that the existence of such a pair of operators is** simply impossible. Therefore, let pred(v) = {w}, where D(w) = {w
′, w′′}**. Without loss of**
generality assume that prv(A1)[w] = {w
′}, prv(A2)[w] = {w
′′}**. Otherwise, if, for instance,**
prv(A1)[w] = u, then it is easy to see that A2 **is a redundant operator.**
Observe that in this case, prevail dependence of v on w **is redundant: We can replace**
the pair of operators A1, A2 in Λ by a single operator A that changes the value of v **from**
v
′to v
′′ without any prevail condition. The replacement of A1, A2 by A **brings us to an**
equivalent problem instance in which the operator set Λv **is post-unique. This way we**
continue to process iteratively all such "problematic" variables v **until we arrive at a postunique problem instance.** 
Proposition 2 There are UB problem instances with a tree causal graph that are not singlevalued, thus TreeUB 6⊂ **UBS.**
Proof: The proof of Proposition 2 is straightforward: Consider a variable v ∈ V, D(v) =
{v
′, v′′}**, such that** succ(v) = {u, w}. It can be the case that any value change of u **will be**
prevailed by v
′, while any value change of w **will be prevailed by** v
′′**. Therefore, restricting**
causal graphs even to trees does not entail single-valuedness.7 Propositions 1 and 2 show that TreeUB is a polynomial subclass of PUB that is not entailed by any tractability results of B¨ackstr¨om and Nebel (1995).

Proposition 3 **There are UB problem instances with a polytree causal graph that are neither single-valued, nor post-unique.**
Proof: **The proof is straightforward: Consider a planning problem with a polytree causal**
graph, such that there exist a variable v ∈ V **with** pred(v) = {u, w}**, and the following**
operator set Λv:

| pre    | post   | prv         |
|--------|--------|-------------|
| v ′    | v ′′   | {u ′ , w′′} |
| ′      | v ′′   | {u ′′, w′}  |
| v v ′′ | v ′    | {u ′ , w′}  |
| v ′′   | v ′    | {u ′′, w′′} |

Clearly, any problem instance with such Λv ⊆ Λ is neither single-valued, nor postunique, since (i) there is more than one operator achieving any value of v**, and (ii) both**
values of u (and both values of w) appear in prevail conditions of the operators in Λv**. Note**