Now, given a planning instance Π, let P be the set of all **irreducible plans for Π. We**
denote by MaxReq(v) the maximal number of times that a variable v ∈ V **changes its value** in the course of execution of an irreducible plan for Π. Formally, let Req(P, v**) be the number**
of times that v changes its value in the course of execution of a plan P**. Then,**

MaxReq(v**) = max**
$$\operatorname*{max}_{P\in{\mathcal{P}}}\{$$
$\overline{\phantom{\rule{0.000pt}{0ex}}\rule{0.000pt}{0.000pt}}$
{Req(**P, v**)}
Observe that, for any planning problem with unary operators, a variable must change its value at most once for each required change of its immediate successors in the causal graph (in order to satisfy the necessary prevail conditions), and then at most once in order to obtain the value requested by the goal. Thus, for all variables in V, MaxReq(v**) satisfies:**

$$\operatorname{MaxReq}(v)\leq1\ +\ \sum_{s u c c(v)}\operatorname{MaxReq}(u)$$
$$(1)$$
MaxReq(u**) (1)**
where succ(v) denotes the immediate successors of v **in the corresponding causal graph.**
Adopting the terminology from (Domshlak & Shimony, 2003; Shimony & Domshlak, 2002),
a directed acyclic graph G is directed-path singly connected if, for every pair of nodes **s, t** ∈ G,
there is at most one directed path from s to t**. The following lemma shows that if the causal**
graph forms a directed-path singly connected DAG then we can **bound** MaxReq(v**) by** n.

Clearly, all polytrees are directed-path singly connected **DAGs, but not vice versa.**
Lemma 1 For any solvable problem instance Π **with a directed-path singly connected causal**
graph over n variables, for any variable v**, we have that** MaxReq(v) ≤ n. Proof: The proof is by induction on n. For n **= 1 it is obvious that** MaxReq(v) ≤ **1. Now**
suppose that when |V| = n − 1 then for any v ∈ V,
MaxReq(v) ≤ n − 1 Let Π′ be some problem instance for which |V′| = n**. Suppose that the variables in** V
′ =
{v1, . . . vn} **are topologically ordered based on the domain's causal graph. Clearly,** vn is a leaf node (i.e., succ (vn) = ∅**). We will denote by Π the problem instance obtained by**
removing vn from the domain, and the corresponding variable set by V**. According to Eq. 1,** for each immediate predecessor v of vn **in the causal graph,**
newMaxReq(v) ≤ MaxReq(v) + newMaxReq(vn) ≤ MaxReq(v**) + 1**
where newMaxReq(v**) denotes** MaxReq(v) with respect to Π′**. Generally, since the causal**
graph is directed-path singly connected, for each variable v ∈ V′,

newMax$\text{Req}(v)\leq\left\{\begin{array}{ll}\text{Max}\text{Req}(v)+1,&\text{if there is a path from}v\text{to}v_{n}\\ \text{Max}\text{Req}(v),&\text{otherwise}\end{array}\right.$ (2)
ob $\psi\subset\lambda^\prime$, b. 
and thus, for each v ∈ V′**, holds**

$${\mathrm{newMaxReq}}(v)\leq n$$
