Pebbling meets coloring: Reversible pebble game on trees

•An exact characterization of reversible pebble number of rooted directed trees.•A polynomial time algorithm to compute the reversible pebble game number of trees.•Estimation of the number of steps needed to optimally pebble various tree families.•Polynomial time pebbling of complete binary trees using almost optimal number of pebbles.•Time-space trade-off for reversible pebbling for families of bounded degree trees.

We show 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. Using this connection as a tool, we also address several questions including that of finding the number of steps required to optimally pebble various families of trees.