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

Fingerprint

Graph in graph theory
NP-complete problem
Target
Unordered
Vertex of a graph
Computational Complexity
Valid
Computing

Keywords

  • Complexity
  • Graph pebbling
  • ∏-completeness

ASJC Scopus subject areas

  • Mathematics(all)

Cite this

The complexity of graph pebbling. / Milans, Kevin; Clark, Bryan.

In: SIAM Journal on Discrete Mathematics, Vol. 20, No. 3, 01.12.2006, p. 769-798.

Research output: Contribution to journalArticle

Milans, Kevin ; Clark, Bryan. / The complexity of graph pebbling. In: SIAM Journal on Discrete Mathematics. 2006 ; Vol. 20, No. 3. pp. 769-798.
@article{9893c2c8177d474e91f182d52ce909cb,
title = "The complexity of graph pebbling",
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.",
keywords = "Complexity, Graph pebbling, ∏-completeness",
author = "Kevin Milans and Bryan Clark",
year = "2006",
month = "12",
day = "1",
doi = "10.1137/050636218",
language = "English (US)",
volume = "20",
pages = "769--798",
journal = "SIAM Journal on Discrete Mathematics",
issn = "0895-4801",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "3",

}

TY - JOUR

T1 - The complexity of graph pebbling

AU - Milans, Kevin

AU - Clark, Bryan

PY - 2006/12/1

Y1 - 2006/12/1

N2 - 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.

AB - 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.

KW - Complexity

KW - Graph pebbling

KW - ∏-completeness

UR - http://www.scopus.com/inward/record.url?scp=34547863895&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34547863895&partnerID=8YFLogxK

U2 - 10.1137/050636218

DO - 10.1137/050636218

M3 - Article

AN - SCOPUS:34547863895

VL - 20

SP - 769

EP - 798

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

SN - 0895-4801

IS - 3

ER -