Abstract
Pebble games are single-player games on DAGs involving placing and moving pebbles on nodes of the graph according to a certain set of rules. The goal is to pebble a set of target nodes using a minimum number of pebbles. In this paper, we present a possibly simpler proof of the result in [4] and strengthen the result to show that it is PSPACE-hard to determine the minimum number of pebbles to an additive \(n^{1/3-\epsilon }\) term for all \(\epsilon > 0\), which improves upon the currently known additive constant hardness of approximation [4] in the standard pebble game. We also introduce a family of explicit, constant indegree graphs with n nodes where there exists a graph in the family such that using \(0< k < \sqrt{n}\) pebbles requires \(\varOmega ((n/k)^k)\) moves to pebble in both the standard and black-white pebble games. This independently answers an open question summarized in [14] of whether a family of DAGs exists that meets the upper bound of \(O(n^k)\) moves using constant k pebbles with a different construction than that presented in [1].
Access provided by CONRICYT-eBooks. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Alwen, J., de Rezende, S.F., Nordström, J., Vinyals, M.: Cumulative space in black-white pebbling and resolution. In: Innovations in Theoretical Computer Science, ITCS 2017, Berkeley, CA, USA, pp. 9–11, January 2017
Alwen, J., Serbinenko, V.: High parallel complexity graphs and memory-hard functions. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14–17, pp. 595–603 (2015). http://doi.acm.org/10.1145/2746539.2746622
Bennett, C.H.: Time/space trade-offs for reversible computation. SIAM J. Comput. 18(4), 766–776 (1989). http://dx.doi.org/10.1137/0218053
Chan, S.M., Lauria, M., Nordström, J., Vinyals, M.: Hardness of approximation in PSPACE and separation results for pebble games. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, October 17–20, 2015, pp. 466–485 (2015). http://dx.doi.org/10.1109/FOCS.2015.36
Cook, S., Sethi, R.: Storage requirements for deterministic / polynomial time recognizable languages. In: Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC 1974, pp. 33–39. ACM, New York (1974). http://doi.acm.org/10.1145/800119.803882
Demaine, E.D., Liu, Q.C.: Inapproximability of the standard pebble game and hard to pebble graphs. CoRR (2017)
van Emde Boas, P., van Leeuwen, J.: Move rules and trade-offs in the pebble game. In: Weihrauch, K. (ed.) GI-TCS 1979. LNCS, vol. 67, pp. 101–112. Springer, Heidelberg (1979). doi:10.1007/3-540-09118-1_12
Gilbert, J.R., Lengauer, T., Tarjan, R.E.: The pebbling problem is complete in polynomial space. In: Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC 1979, pp. 237–248. ACM, New York (1979). http://doi.acm.org/10.1145/800135.804418
Gilbert, J.R., Tarjan, R.E.: Variations of a pebble game on graphs. Technical report, Stanford, CA, USA (1978)
Hertel, P., Pitassi, T.: The PSPACE-completeness of black-white pebbling. SIAM J. Comput. 39(6), 2622–2682 (2010). http://dx.doi.org/10.1137/0218053
Hopcroft, J., Paul, W., Valiant, L.: On time versus space. J. ACM 24(2), 332–337 (1977). http://doi.acm.org/10.1145/322003.322015
Jia-Wei, H., Kung, H.T.: I/O complexity: the red-blue pebble game. In: Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing, STOC 1981, pp. 326–333. ACM, New York (1981). http://doi.acm.org/10.1145/800076.802486
Lengauer, T., Tarjan, R.E.: Upper and lower bounds on time-space tradeoffs. In: Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC 1979, pp. 262–277. ACM, New York (1979). http://doi.acm.org/10.1145/800135.804420
Nordstrom, J.: New wine into old wineskins: A survey of some pebbling classics with supplemental results (2015)
Paul, W.J., Tarjan, R.E., Celoni, J.R.: Space bounds for a game on graphs. In: Proceedings of the Eighth Annual ACM Symposium on Theory of Computing, STOC 1976, pp. 149–160. ACM, New York (1976). http://doi.acm.org/10.1145/800113.803643
Sethi, R.: Complete register allocation problems. SIAM J. Comput. 4(3), 226–248 (1975). http://dx.doi.org/10.1137/0204020
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Demaine, E.D., Liu, Q.C. (2017). Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs. In: Ellen, F., Kolokolova, A., Sack, JR. (eds) Algorithms and Data Structures. WADS 2017. Lecture Notes in Computer Science(), vol 10389. Springer, Cham. https://doi.org/10.1007/978-3-319-62127-2_27
Download citation
DOI: https://doi.org/10.1007/978-3-319-62127-2_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-62126-5
Online ISBN: 978-3-319-62127-2
eBook Packages: Computer ScienceComputer Science (R0)