Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs
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 stre...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Nature
2019
|
| Online Access: | https://hdl.handle.net/1721.1/121351 |
| _version_ | 1826211944748548096 |
|---|---|
| author | Demaine, Erik D Liu, Quanquan |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Demaine, Erik D Liu, Quanquan |
| author_sort | Demaine, Erik D |
| collection | MIT |
| description | 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 n1/3−εterm for all ε > 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 < √n pebbles requires Ω((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(nk) moves using constant k pebbles with a different construction than that presented in [1]. |
| first_indexed | 2024-09-23T15:13:53Z |
| format | Article |
| id | mit-1721.1/121351 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:13:53Z |
| publishDate | 2019 |
| publisher | Springer Nature |
| record_format | dspace |
| spelling | mit-1721.1/1213512022-10-02T01:32:31Z Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs Demaine, Erik D Liu, Quanquan Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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 n1/3−εterm for all ε > 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 < √n pebbles requires Ω((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(nk) moves using constant k pebbles with a different construction than that presented in [1]. 2019-06-18T19:49:06Z 2019-06-18T19:49:06Z 2017-07 2019-06-17T16:27:42Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/121351 Demaine E.D. and Q.C. Liu. "Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs." Workshop on Algorithms and Data Structures 2017, July-August 2017, St. Johns, Canada, Springer International Publishing, July 2017 © 2017 Springer International Publishing en http://dx.doi.org/10.1007/978-3-319-62127-2_27 Workshop on Algorithms and Data Structures 2017 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer Nature arXiv |
| spellingShingle | Demaine, Erik D Liu, Quanquan Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs |
| title | Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs |
| title_full | Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs |
| title_fullStr | Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs |
| title_full_unstemmed | Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs |
| title_short | Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs |
| title_sort | inapproximability of the standard pebble game and hard to pebble graphs |
| url | https://hdl.handle.net/1721.1/121351 |
| work_keys_str_mv | AT demaineerikd inapproximabilityofthestandardpebblegameandhardtopebblegraphs AT liuquanquan inapproximabilityofthestandardpebblegameandhardtopebblegraphs |