The complexity of graph pebbling

被引:35
作者
Milans, Kevin [1 ]
Clark, Bryan
机构
[1] Univ Illinois, Dept Comp Sci, Urbana, IL 61801 USA
[2] Univ Illinois, Dept Phys, Urbana, IL 61801 USA
关键词
graph pebbling; complexity; Pi(P)(2)-completeness;
D O I
10.1137/050636218
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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 (pi) over cap (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 p( 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 (pi) over cap (G) and pi(G). In particular, we show that deciding whether (pi) over cap (G) <= k is NP-complete. Furthermore, we prove that deciding whether pi(G) <= k is Pi(P)(2)-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.
引用
收藏
页码:769 / 798
页数:30
相关论文
共 15 条
[11]  
Papadimitriou C.H., 1994, Computational Complexity
[12]  
SJOSTRAND J, 2005, ELECT J COMBIN, V12
[13]   A SIMPLIFIED NP-COMPLETE SATISFIABILITY PROBLEM [J].
TOVEY, CA .
DISCRETE APPLIED MATHEMATICS, 1984, 8 (01) :85-89
[14]  
VUONG A, CONDITIONS WEIGHTED
[15]  
WATSON NG, 2005, COMPLEXITY PEBBLING