The complexity of pebbling reachability and solvability in planar and outerplanar graphs

详细信息    查看全文

• 作者：Timothy Lewis ^{timothy.lewis@hope.edu" class="auth_mail} ; Charles A. Cusack ; ^{cusack@hope.edu" class="auth_mail} ; Lisa Dion¹ ; ^{lisadion@umich.edu" class="auth_mail}
• 关键词：Graph pebbling ; Planar ; Outerplanar ; NP-complete
• 刊名：Discrete Applied Mathematics
• 出版年：31 July 2014
• 年：2014
• 卷：172
• 期：Complete
• 页码：62-74
• 全文大小：562 K

文摘

Given a simple, connected graph, a pebbling configuration   is a function from its vertex set to the nonnegative integers. A pebbling move   between adjacent vertices removes two pebbles from one vertex and adds one pebble to the other. A vertex r$r$ is said to be reachable   from a configuration if there exists a sequence of pebbling moves that places at least one pebble on r$r$. A configuration is solvable   if every vertex is reachable. We prove that determining reachability of a vertex and solvability of a configuration are NP-complete on planar graphs. We also prove that both reachability and solvability can be determined in O(n⁶)$O\left(n^6\right)$ time on planar graphs with diameter two. Finally, for outerplanar graphs, we present a linear algorithm for determining reachability and a quadratic algorithm for determining solvability. To prove this result, we provide linear algorithms to determine all possible maximal configurations of pebbles that can be placed on the endpoints of a path and on two adjacent vertices in a cycle.