The complexity of graph pebbling

Kevin Milans, Bryan Clark

Research output: Contribution to journalArticle

Abstract

In a graph G whose vertices contain pebbles, a pebbling move uv removes two pebbles from u and adds one pebble to a neighbor v of u. The optimal pebbling number π̂(G) is the minimum k such that there exists a distribution of k pebbles to G so that for any target vertex r in G, there is a sequence of pebbling moves which places a pebble on r. The pebbling number π(G) is the minimum k such that for all distributions of k pebbles to G and for any target vertex r, there is a sequence of pebbling moves which places a pebble on r. We explore the computational complexity of computing π̂(G) and π(G). In particular, we show that deciding whether π̂(G) ≤ k is NP-complete. Furthermore, we prove that deciding whether π(G) ≤ k is ∏2P-complete and therefore both NP-hard and coNP-hard. Additionally, we provide a characterization of when an unordered set of pebbling moves can be ordered to form a valid sequence of pebbling moves.

Original languageEnglish (US)
Pages (from-to)769-798
Number of pages30
JournalSIAM Journal on Discrete Mathematics
Volume20
Issue number3
DOIs
StatePublished - Dec 1 2006

Keywords

  • Complexity
  • Graph pebbling
  • ∏-completeness

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'The complexity of graph pebbling'. Together they form a unique fingerprint.

  • Cite this