The Complexity of Graph Pebbling

2005/03/30 by K. Milans, Milans, K., B. Clark +1 · 3 citations
Mathematics · #05C99 #68Q17 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C99 #msc:68Q17

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

24 pages, 6 figures

arxiv created 2005/03/30 · arxiv updated 2009/12/01

Abstract

We explore the complexity of computing the optimal pebbling number and pebbling number of a graph. We show that deciding whether the optimal pebbling number of G is at most k is NP-complete and deciding whether the pebbling number of G is at most k is Π₂-complete. Additionally, we provide a characterization of when an unordered set of pebbling moves can be ordered to form a valid sequence of pebbling moves.

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

• A linear optimization technique for graph pebbling
• Optimal pebbling number of graphs with given minimum degree
• The Complexity of Pebbling and Cover Pebbling
• Restricted optimal pebbling is NP-hard
• Automating Weight Function Generation in Graph Pebbling