It is easy to see that the causal graph of this problem forms a DAG (see Figure 7), and an instance of this planning problem with the initial state h0, . . . , 0i **and the goal state**
h0, . . . , 0, 1i has a unique minimal solution of length 2n − **1 corresponding to a Hamilton**
path in the state space.

![0_image_0.png](0_image_0.png)

Now we show that this escalation in complexity can be "parametrized" by the form of the causal graph.

Lemma 3 For any solvable problem instance Π with an acyclic causal graph over n variables, for any variable v**, we have that:**

$$\mathrm{MaxReq}(v_{i})\leq1\ +\ \sum_{j=i+1}^{n}\rho(v_{i},v_{j})$$

where ρ(vi, vj ) **denotes the total number of different, not necessary disjoint, paths from** vi to vj **, where variables are ordered via a topological sort of the causal graph.**
Proof: The proof is by induction on i. For i = n **it is obvious that** MaxReq(vn) ≤ 1.

Now we assume that the lemma holds for any i > k, and prove it for i = k**. Without loss**
of generality, assume that succ(vk) 6= ∅**. Otherwise, we simply have that** MaxReq(vk) ≤ 1.

The proof is straightforward:

$$\begin{array}{ccccccccc}\mbox{MaxSeq}(v_{k})&\stackrel{{Eq.\ 1}}{{\leq}}&1&+&\sum_{v_{i_{k}}\in succ(v_{k})}&\mbox{MaxSeq}(v_{i_{k}})\leq\\ &&&&\\ &&&&\\ \stackrel{{I.H.}}{{\leq}}&1+|\mbox{succ}(v_{k})|+\sum_{v_{i_{k}}\in succ(v_{k})}\sum_{j=i_{k}+1}^{n}\rho(v_{i_{k}},v_{j})=\\ &&&&\\ =&1+\sum_{j=k+1}^{n}\rho(v_{k},v_{j})\end{array}$$

![0_image_1.png](0_image_1.png)

## 

Lemma 3 entails that the upper bound for MinPlanSize**(Π) for a general planning problem**
with unary operators and acyclic causal graph depends on the **number of different paths** between the nodes in the causal graph. An immediate conclusion is that there is a significant class of problems with an acyclic causal graph for which planning is in np**. Let a DAG be**
called max-δ-connected **if the number of different directed paths between every two nodes** in this graph is bounded by δ.