Pebbling meets coloring: reversible pebble game on trees

DOI10.1016/J.JCSS.2017.07.009zbMATH Open1378.68085arXiv1604.05510OpenAlexW2962848491MaRDI QIDQ2409574FDOQ2409574

Authors: Balagopal Komarath, Saurabh Sawlani, Jayalal Sarma M. N. 

Publication date: 11 October 2017

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Abstract: 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(loglog(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^{e}psilon)$ pebbles in $O(n)$ steps. This generalizes an analogous result of Kralovic (2001) for chains.

Full work available at URL: https://arxiv.org/abs/1604.05510

Recommendations

• Reversible pebble game on trees
• Time and space complexity of reversible pebbling
• Inapproximability of the standard pebble game and hard to pebble graphs
• scientific article; zbMATH DE number 3952825
• scientific article; zbMATH DE number 3976363

zbMATH Keywords

combinatoricsreversible pebblingedge-rank coloringpebbling games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Games on graphs (graph-theoretic aspects) (05C57)

Cites Work

• Title not available (Why is that?)
• A polynomial algorithm for the min-cut linear arrangement of trees
• Speedups of deterministic machines by synchronous parallel machines
• Complete Register Allocation Problems
• Time/Space Trade-Offs for Reversible Computation
• The Pebbling Problem is Complete in Polynomial Space
• The PSPACE-Completeness of Black-White Pebbling
• Title not available (Why is that?)

Cited In (5)

• Improved reversible and quantum circuits for Karatsuba-based integer multiplication
• The Scholten/Dijkstra Pebble Game Played Straightly, Distributedly, Online and Reversed
• Nullstellensatz size-degree trade-offs from reversible pebbling
• Nullstellensatz size-degree trade-offs from reversible pebbling
• Reversible pebble game on trees

This page was built for publication: Pebbling meets coloring: reversible pebble game on trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2409574)