General trees

We now generalize the above algorithm to an arbitrary tree. First, for a leaf node $v$, we define $f_v (k, \ell)$ to be the minimal cost $c(P)$ of all feasible pebbling $P$ of $(T_v,k)$ with at most $\ell$ pebbles in $T_v$, and where if $k > 0$ we stipulate that one additional pebble is placed at the tip of the external path from $v$. Note that in the case of leaf node, $T_v$ is a singleton, and if $k > 0$ then $(T_v,k)$ is a single path of length $k$. Also $0 \le \ell \le L_v = 1$, and $0 \le k \le d_v$.

Thus, the computation for the leaves are identical to that in the binary tree. If $k=0$, then

$$f_v (0, 0) = \left\{ \begin{array}{cl} 0 & \mbox{if $w[v] = 0$}\\ \infty & \mbox{otherwise,} \end{array} \right.$$

and for $\ell = 1$,

$$f_v (0, 1) = w[v].$$

For $k \ge 1$,

$$f_v (k, 0) = (k+1) \cdot w[v],$$

and for $\ell = 1$,

$$f_v (k, 1) = w[v].$$

We now consider non-leaf nodes $v$. Let $\Delta$ be the number of children of $v$, let $v_1, v_2, \ldots, v_{\Delta}$ be its children from left to right, and let the subtrees rooted at the children of $v$ be $T_{v, 1}, T_{v, 2}, \ldots, T_{v, \Delta}$ respectively. Denote by $T_{v, [d]}$ the subtree of $T_v$ induced by the vertex set of $\{v\} \cup \bigcup_{i=1}^{d} T_{v, i}$, for $1 \le d \le \Delta$. Denote by $L_{v, d}$ the total number of leaves in $T_{v, [d]}$.

Define $f_{v, d}^{b}(k, \ell)$, where $b=0$ or $1$, $1 \le d \le \Delta$, $0 \le \ell \le L_{v, d}$, and $0 \le k \le d_v$, as follows. First let $k=0$. If $b=0$, $f_{v, d}^{0}(0, \ell)$ is the minimal cost of a pebbling placement of the subtree $T_{v, [d]}$, where we use at most $\ell$ pebbles in $T_{v, [d]}$, and no pebble is placed on $v$. (When no feasible pebbling placement exists with this constraint we have $f_{v, d}^{0}(0, \ell) = \infty$.) If $b=1$, $f_{v, d}^{1}(0, \ell)$ is the same as above except $v$ is placed with a pebble out of $\ell$ pebbles.

This definition is generalized for $k \ge 0$. For $f_{v, d}^{b}(k, \ell)$, we consider $(T_{v, [d]}, k)$ in place of $T_{v, [d]}$ and for $k > 0$ we stipulate that one additional pebble is placed at the tip of the external path from $v$ of distance $k$ from $v$. As before this additional pebble is not counted in $\ell$.

We then define

$$f_{v}^{b}(k, \ell) = f_{v, \Delta}^{b}(k, \ell),$$

and

$$f_{v}(k, \ell) = \min\{ f_{v}^{0}(k, \ell), f_{v}^{1}(k, \ell) \}.$$

Again we will compute $f_v (k, \ell)$ for all $k, \ell \ge 0$, inductively for $v$ according to the height of the subtree $T_v$, starting with leaves $v$. The base case $h=0$ having already been taken care of, we assume $h>0$ and $h(T_v) = h$.

First we consider the left most subtree $(T_{v, 1}$ with $d=1$, i.e., we compute $f_{v, 1}^{b}(k, \ell)$ for $(T_{v, [1]}, k)$.

If $k=0$ and $b=0$, then

$$f_{v, 1}^{0}(0, \ell) = f_{v_1}(0, \ell).$$

Note that $h(T_{v_1}) < h$ and thus inductively $f_{v_1}(k, \ell)$ have been all computed already.

Similarly for $k=0$ and $b=1$, then

$$f_{v, 1}^{1}(0, \ell) = \left\{ \begin{array}{cl} \infty & \... ...{v_1}(1, \ell-1) & \mbox{if $\ell \ge 1$.} \end{array} \right.$$

Note that in the last equation the ``$k$'' value in $f_{v_1}$ is 1 due to the stipulation that by $b=1$ we placed a pebble on $v$.

Now we consider $k \ge 1$. Again if $b=0$,

$$f_{v, 1}^{0}(k, \ell) = f_{v_1}(k+1, \ell).$$

Similarly for $k \ge 1$ and $b=1$,

$$f_{v, 1}^{1}(0, \ell) = \left\{ \begin{array}{cl} \infty & \... ...{v_1}(1, \ell-1) & \mbox{if $\ell \ge 1$.} \end{array} \right.$$

We proceed to the case of $1 < d \le \Delta$. This time we inductively assume that we have already computed not only all $f_{v'} (k, \ell)$ with $h(T_{v'}) < h$, but also the relevant quantities for $(T_{v, [d-1]}, k)$.

Thus, for $k=0$ and $b=0$,

$$f_{v, d}^{0}(0, \ell) = \min_{\ell' + \ell'' = \ell} \{ f_{v, d-1}^{0}(0, \ell') + f_{v_d}(0, \ell'') \}.$$

To be precise the minimization is over all pairs $(\ell', \ell'')$, such that $0 \le \ell' \le L_{v, d-1}$, $0 \le \ell'' \le L_{v_d}$ and $\ell_1 + \ell_2 = \ell \le L_{v,d}$.

For $k=0$ and $b=1$,

$$f_{v, d}^{1}(0, \ell) = \min_{\ell' + \ell'' = \ell} \{ f_{v, d-1}^{1}(0, \ell') + f_{v_d}(1, \ell'') \}.$$

Note that in $f_{v_d}$ we had the ``$k$'' value 1 since by $b=1$ we have stipulated that a pebble is placed on $v$. The range of $(\ell', \ell'')$ are the same as before except in fact $\ell'$ must be $\ge 1$, otherwise the value $\infty$ will appear. (In particular, for $\ell = 0$ the minimization is $\infty$.)

Finally we consider the case $d >1$ and $1 \le k \le d_v$. For $k \ge 1$ and $b=0$, we have

$$f_{v, d}^{0}(k, \ell) = \min_{\ell' + \ell'' = \ell} \{ f_{v, d-1}^{0}(k, \ell') + f_{v_d}(k+1, \ell'') \}.$$

And for $k \ge 1$ and $b=1$, we have

$$f_{v, d}^{1}(k, \ell) = \min_{\ell' + \ell'' = \ell} \{ f_{v, d-1}^{1}(k, \ell') + f_{v_d}(1, \ell'') \}.$$

Note that in the last equation, in fact the minimization is over all pairs $(\ell', \ell'')$ with $\ell' \ge 1$, as well as $\ell' \le L_{v, d-1}$, $0 \le \ell'' \le L_{v_d}$ and $\ell_1 + \ell_2 = \ell \le L_{v,d}$. But we do not need to explicitly state that $\ell' \ge 1$, since for $\ell' =0$, $f_{v, d-1}^{1}(k, 0) =\infty$ can be shown by an easy induction. Also note that the ``$k$'' value in $f_{v_d}$ is 1, due to the stipulation by $b=1$ that $v$ is pebbled by one of the $\ell'$ pebbles.

We have completed the description of the algorithm. The final answer is $f_{r} (0, m)$, where $r$ is the root of $T$ and $m$ is the number of pebbles. Again, no need to compute for any value $\ell > m$, if $m$ is the total number of pebbles given.

The complexity of the algorithm can be easily estimated as before. For leaves, the algorithm spends $O(d_v) =O(H)$ time per leaf. Thus the total work spent on leaves is at most $O(nH)$. For any non-leaf $v$, suppose the degree of $v$ is $\Delta_v$, then the computation work spent for $v$ is $O(\Delta_v H m^2)$. Thus the total amount of work spent for non-leaves is $O(\sum_{v} \Delta_v H m^2) = O(n H m^2)$. Hence the total running time is at most $O(n H m^2)$, which is again only $O(n m^2 \log n)$ with $H \approx O(\log n)$.

Theorem 2   There is a polynomial time algorithm that computes the optimal pebbling placement as well as the optimal cost of the pebbling placement. The running time is $O(n H m^2)$, for any rooted tree of $n$ vertices, height $H$, and $m$ pebbles.