The Complexity of Pebbling and Cover Pebbling

2005/03/24 by Nathaniel G. Watson, Watson, Nathaniel G. · 3 citations
Computer Science · Mathematics · #05C35 #05C99 #68Q17 #Cellular Automata and Applications #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C35 #msc:05C99 #msc:68Q17

paper · pdf · doi:10.48550/arxiv.math/0503511

20 pages, 3 figures

openalex publication_date 2005/03/24 · arxiv created 2005/04/21 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Conditions for Weighted Cover Pebbling of Graphs

Cited by

• Applying Hurlbert's Linear Optimization Technique to Establish Bounds on Pebbling Numbers
• The only Class 0 Flower snark is the smallest
• A Weight Function Lemma Heuristic for Graph Pebbling

Related

• Threshold and Complexity Results for the Cover Pebbling Game
• The Complexity of Graph Pebbling
• The Cover Pebbling Number of Graphs
• The cover pebbling theorem
• Cover pebbling numbers and bounds for certain families of graphs