Binary tree case

We first consider the case of binary trees, where every vertex has at most two children. Of course it is a leaf when there are no children. Thus for non-leaves, there are either a unique child, or there are two children, in which case we order them as left and right arbitrarily.

For any vertex $v$ of the tree $T$, denote the subtree rooted at $v$ by $T_v$. Generically, if $v$ has a unique child then we denote that child by $v_1$, and if there are two children then we denote them $v_1$ and $v_2$ respectively. For $k \ge 0$ we consider a tadpole graph $(T,k)$ defined as $T$ appended by a single path extending upwards from the root of $T$ with $k$ extra vertices. Note that $(T,0) = T$.

For $\ell \geq 0$, We will consider the optimal placement of at most $\ell$ pebbles in $T_v$, and denote the minimal cost by $f_v (0, \ell)$. More generally, for $k > 0$ and $\ell \geq 0$, we will consider the optimal placement of one pebble at the tip of the sperm graph $(T_v,k)$ which has distance $k$ from the root $v$ of $T_v$, and at most $\ell$ pebbles within $T_v$. We denote by $f_v (k, \ell)$ the minimal cost $c(P)$ of all feasible pebbling $P$ of $(T,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$. If $k=0$ and $\ell = 0$ then we have a feasible pebbling if and only if all weights in $T_v$ are zero, in which case $f_v (0, 0) = 0$. Note that for any $k, \ell \ge 0$ and $k+\ell \geq 1$, a feasible pebbling exists. For $k = \ell=0$, and if some non-zero weights exist in $T_v$, and thus no feasible pebbling exists, we denote $f_v (0, 0) = \infty$.

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$.

More formally, let $L_v$ be the number of leaves in $T_v$. Let $d_v = d_v(T)$ be the depth of $v$ in $T$, i.e., the distance from the root of $T$ to $v$ (note that by our definition of distance, the depth of the root is 0). Let $h(T_v)$ be the height of the tree $T_v$, which is the maximum depth of all leaves in $T_v$, i.e., $h(T_v) = \max_{u} d_u(T_v)$, where $u$ ranges over all leaves in $T_v$. Note that a tree with a singleton vertex has height 0. Inductively for $0 \le h \le h(T)$, starting with $h=0$, we compute $f_v (k, \ell)$, for all $v \in T$ such that the subtree $T_v$ has $h(T_v) = h$, and for all $0 \le k \le d_v$, and for all $0 \le \ell \le L_v$.

Base Case $h=0$:
In the base case $h=0$ and we are dealing with a singleton leaf, together with an extension of a path of length $k$ if $k > 0$, and no extensions if $k=0$.

Thus, for $k=0$,

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

and for $\ell = 1$, (note that $h(T_v) = h= 0$ implies that $L_v =1$),

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

Now for $k \ge 1$,

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

and for $\ell = 1$,

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

Inductive Case $h>0$:
For the inductive case $h>0$, we have some $v$ with $h(T_v) = h$, and we assume we have computed all $f_{v'} (k, \ell)$ for children $v'$ of $v$. There are two cases, $v$ has either one or two children. First we consider $v$ has a unique child $v_1$. For either $k=0$ or $k > 0$, we can consider either placing a pebble at $v$ or not placing it there. But we claim that without loss of generality we don't need to place it there. This is because $v$ has only one child, and if an optimal pebbling places a pebble at $v$, we can obtain at least as good a pebbling by moving the pebble from $v$ to $v_1$, and if $v_1$ is already pebbled we can remove one pebble. Thus, we have an optimal pebbling of $(T_v,k)$ using at most $\ell$ pebbles in $T_v$ without a pebble at $v$. Hence,

$$f_{v} (0, \ell) = f_{v'} (0, \ell),$$

and for $k > 0$,

$$f_{v} (k, \ell) = f_{v'} (k+1, \ell).$$

Suppose now $v$ has two children $v_1$ and $v_2$. Basically we must decide how to distribute $\ell$ pebbles in the subtrees $T_{v_1}$ and $T_{v_2}$ with $\ell_1$ and $\ell_2$ pebbles each. There is a slight complication as to whether to place a pebble at $v$, the root of $T_v$, which affects how many pebbles there are to be distributed, either $\ell_1 + \ell_2 = \ell$ or $\ell -1$.

First $k=0$. If we place a pebble at $v$, (which of course presupposes $\ell >0$), then there are $\ell_1 + \ell_2 = \ell -1$ pebbles to be distributed in $T_{v_1}$ and $T_{v_2}$, but with respect to these two subtrees the ``$k$'' values are both 1, i.e., we have $f_{v_1} (1, \ell_1) + f_{v_2} (1, \ell_2)$, minimized over all pairs $\ell_1 + \ell_2 = \ell -1$. (To be precise, all pairs $(\ell_1, \ell_2)$, such that $0 \le \ell_1 \le L_{v_1}$, $0 \le \ell_2 \le L_{v_2}$ and $\ell_1 + \ell_2 = \ell -1$; but we will not specify this range explicitly in the following.)

If we don't place a pebble at $v$, then there are $\ell_1 + \ell_2 = \ell$ pebbles to be distributed in $T_{v_1}$ and $T_{v_2}$, and since $k=0$ for $T_v$, with respect to these two subtrees we still have the ``$k$'' values 0. So we have $f_{v_1} (0, \ell_1) + f_{v_2} (0, \ell_2)$, minimized over all pairs $\ell_1 + \ell_2 = \ell$.

The optimal cost $f_{v} (0, \ell)$ is the minimum of these two minimizations, i.e.,

$$f_{v} (0, \ell) = \min \left\{ \min_{\ell_1 + \ell_2 = \ell -... ...\ell} \{ f_{v_1} (0, \ell_1) + f_{v_2} (0, \ell_2) \} \right\}.$$

(It is understood that in case $\ell = 0$, the first minimization is vacuous and should be omitted. This is the standard convention, a minimization over an empty set (no non-negative $\ell_i$ sum to $-1$) is $\infty$. Also the second minimization is merely $f_{v_1} (0, 0) + f_{v_2} (0,0)$ which is typically $\infty$ unless all weights in $T_v$ are zero, in which case it is 0.)

We consider the case $k \ge 1$ next. For $\ell = 0$ we have

$$f_{v} (k, 0) = f_{v_1} (k+1, 0) + f_{v_2} (k+1, 0).$$

Suppose $\ell >0$. Again we have the possibilities of placing a pebble at $v$ or not. Thus,

$$f_{v} (k, \ell) = \min \left\{ \min_{\ell_1 + \ell_2 = \ell -... ...} \{ f_{v_1} (k+1, \ell_1) + f_{v_2} (k+1, \ell_2) \} \right\}.$$

This completes the description of the computations of $f_{v} (k, \ell)$. The final answer is $f_{r} (0, m)$, where $r$ is the root of $T$ and $m$ is the number of pebbles. If $m$ is given, (typically much smaller than the number of leaves), in the above computations one never needs to compute for $\ell$, the number of pebbles allowed, beyond $m$, i.e., all $\ell \le m$.

We estimate the complexity of the algorithm. Let $H = h(T)$ be the height of the tree. Typically $H \approx O(\log n)$. For leaves, the algorithm spends $O(d_v) =O(H)$ time per leaf. For each vertex with one child the time is $O(d_v \min\{L_v, m\}) = O(H m)$. For each vertex with two children it is $O(d_v \min\{L_v, m\}^2) = O(H m^2)$. Hence the total running time is at most $O(n H m^2)$, which is only $O(n m^2 \log n)$ with $H \approx O(\log n)$.

It is also clear that the above algorithm can be easily modified to compute the actual optimal algorithm in addition to the optimal cost.

Theorem 1   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 a binary tree of $n$ vertices, height $H$, and $m$ pebbles.