Pebbling meets coloring: reversible pebble game on trees

DOI10.1016/J.JCSS.2017.07.009MaRDI QIDQ2409574zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1303585 (Why is no real title available?)
• scientific article; zbMATH DE number 2080928 (Why is no real title available?)
• A polynomial algorithm for the min-cut linear arrangement of trees
• Complete Register Allocation Problems
• Speedups of deterministic machines by synchronous parallel machines
• The PSPACE-Completeness of Black-White Pebbling
• The Pebbling Problem is Complete in Polynomial Space
• Time/Space Trade-Offs for Reversible Computation

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)