  The reversible pebble game is a combinatorial game played on rooted DAGs.
This game was introduced by Bennett (1989) motivated by applications in
designing space efficient reversible algorithms. Recently, Chan (2013) showed
that the reversible pebble game number of any DAG is the same as its
Dymond-Tompa pebble number and Raz-Mckenzie pebble number.
  We show, as our main result, that for any rooted directed tree T, its
reversible pebble game number is always just one more than the edge rank
coloring number of the underlying undirected tree U of T. It is known that
given a DAG G as input, determining its reversible pebble game number is
PSPACE-hard. Our result implies that the reversible pebble game number of trees
can be computed in polynomial time.
  We also address the question of finding the number of steps required to
optimally pebble various families of trees. It is known that trees can be
pebbled in $n^{O(\log(n))}$ steps where $n$ is the number of nodes in the tree.
Using the equivalence between reversible pebble game and the Dymond-Tompa
pebble game (Chan, 2013), we show that complete binary trees can be pebbled in
$n^{O(\log\log(n))}$ steps, a substantial improvement over the naive upper
bound of $n^{O(\log(n))}$. It remains open whether complete binary trees can be
pebbled in polynomial (in $n$) number of steps. Towards this end, we show that
almost optimal (i.e., within a factor of $(1 + \epsilon)$ for any constant
$\epsilon > 0$) pebblings of complete binary trees can be done in polynomial
number of steps.
  We also show a time-space trade-off for reversible pebbling for families of
bounded degree trees by a divide-and-conquer approach: for any constant
$\epsilon > 0$, such families can be pebbled using $O(n^\epsilon)$ pebbles in
$O(n)$ steps. This generalizes an analogous result of Kralovic (2001) for
chains.
