The Complexity of Pebbling and Cover Pebbling

Abstract

This paper discusses the complexity of graph pebbling, dealing with both traditional pebbling and the recently introduced game of cover pebbling. Determining whether a configuration is solvable according to either the traditional definition or the cover pebbling definition is shown to be NP-complete. The problem of determining the cover pebbling number for an arbitrary demand configuration is shown to be NP-hard.

20 pages, 3 figures

References in corpus (4)

• A Survey of Graph Pebbling
• Conditions for Weighted Cover Pebbling of Graphs
• Cover pebbling numbers and bounds for certain families of graphs
• The Complexity of Graph Pebbling

Cited by in corpus (1)

• Recent Progress in Graph Pebbling