Fractional PebblingMany combinatorial optimization parameters have fractional counterparts. Graph parameters like chromatic number and matching number [ScUl] are well known examples, as is the dimension of posets [BrSc], and the pebbling number is no exception. Let $\pi(G,k)$ be the minimum $t$ such that, for every choice of root $r$ and for every configuration of $t$ pebbles on $G$, it is possible to move $k$ pebbles to $r$. Then the fractional pebbling number $\hat{\pi}(G)=\liminf_{k \rightarrow \infty}\pi(G,k)/k$. (Because $\pi(G,sk) \leq s \pi(G,k)$ for all $s > 0$, we can replace $\liminf$ by $\lim$ in the definition.) For example, $\hat{\pi}(K_n) = \liminf_{k \rightarrow \infty}(n+2k-2)/k=2$. Also, using Chung's Pebbling Tree Theorem [Chu], it is easy to compute $\hat{\pi}(T)=2^{{\rm diam}(T)}$ for every tree $T$. Based on this and other evidence, Hurlbert made the following conjecture.ComplexityFractional Pebbling Conjecture. For every graph $G$ we have that $\hat{\pi}(G)=2^{{\rm diam}(G)}$.Typically, the parameter in question can be formulated in terms of an integer linear program, and the relaxation of the program gives rise to the fractional version of the parameter. In the case of graph pebbling, while it is routine to verify in polynomial time that a particular configuration reaches a particular root, no simple matrix condition as yet exists to capture whether every configuration of a fixed size $t$ is solvable for a particular root. Thus minimizing $t$ as an integer program remains elusive, and so it is difficult to say at present whether or not a parameter exists that is dual to $\pi$. Lourdusamy and Somasundaram [LoSo] found a proof that verifies Graham's Conjecture for the case $C_5 \times C_5$. Their proof uses linear programming and lends credence to the above ideas while suggesting that further explorations into the connections between linear programming duality and pebbling numbers may be fruitful and worthwhile indeed.Because it is easy to verify a pebbling solution, the question of deciding whether a given configuration $C$ reaches a given root $r$ is in NP. In fact it has been shown [HuKi] that this question is at least as hard as NP-complete. (see also [MiCl, Wat]).ApproximationsComplexity Lower Bound. For every $4$-regular hypergraph $H$, there is a graph $G$, a configuration $C$, and a root $r$, so that deciding if $C$ reaches $r$ in $G$ is at least as hard as deciding if $H$ has a perfect matching.The following complexity upper bound is found in [MiCl].Complexity Upper Bound. Deciding whether $\pi(G) \leq k$ is $a$ $\Pi_2^P-complete$ problem.This means that it is complete for the class of languages computable in polynomial time by co-NP machines equipped with an oracle for an NP-complete language. They also proved that deciding whether $\pi^*(G) \leq k$ is NP-complete, while the same result is proved in [Wat] for deciding whether $\gamma(G) \leq k$.Instead of computing $\pi(G)$ exactly, one could try to approximate it. In other words the following question is of interest.Greedy AlgorithmsPebbling Approximation Question. Does there exist a (constant/linear/polynomial) function $F(n)$ and an algorithm which, given a graph $G$ on $n$ vertices, can find a number in polynomial time $\overline{\pi}(G)$ such that $|\pi(G)-\overline{\pi}(G)| \leq F(n)$?Just like in the case of other "hard" problems one can design a "good" approximation algorithm for special cases of graphs. In particular, is it possible to design an approximation algorithm for the case when $G$ is a dense graph? Perhaps an easier and more natural question is to ask for an algorithm which, given a configuration and a root, will pebble to the root efficiently.Pebbling Solution Question. Does there exist an algorithm which, given a graph $G$, a root $r$, and an $r$-solvable configuration $C$, can pebble to $r$ in time polynomial in $n$?Of course, the Complexity Lower Bound shows that this is in general impossible unless P = NP, although the question for appropriately restricted classes of graphs, such as cubes, remains interesting.A solution is greedy (semi-greedy) if every step in the solution is greedy. A graph $G$ is greedy if every configuration of size $\pi(G)$ has a greedy soultion. Trees, cubes, and products of paths are greedy [CHH]. The $5$-cycle $abcde$ is not yet greedy, as witnessed by the configuration $C(c,d)=(3,2)$ with root $a$. Worse yet, let $H$ be the graph formed from the $6$-cycle $abcdef$ by adjoining new vertices $g$ to $a$ and $c$, and $h$ to $a$ and $e$. It is not difficult to show that $f(H)=9$. Then the configuration $C(a,b,f,g,h)=(1,3,3,1,1)$ is not semi-greedily $d$-solvable, so $H$ is not semi-greedy.ReferencesConsider (see) the book $B_{3,3}=P_3 \times S_4$ ($S_4$ is the star $K_{1,3}$). Both $P_3$ and $K_{1,3}$ are greedy because they are trees. However, $B_{3,3}$ is not even semi-greedy. Indeed, think of $B_{3,3}$ as the pages of a book, let $r$ be the corner vertex of one of the pages, $x$ the farthest corner vertex of a second page, $u$, $v$, and $w$ the three vertices of the third page, and let $C(u,v,w,x)=(1,1,1,15)$. From the Practice section we know that $\pi(B_{3,3})=18$, so $C$ is solvable. However, $C$ has no greedy solution. This shows that even semi-greediness is not always preserved by cartesian product. This is especially disappointing since it shoots down a promising method of attack on Graham's Conjecture. Knowing that a graph is greedy would be of great aid in solving some pebbling configuration on the graph via computer. Thus it is worth attempting to characterize greedy graphs, or at least building up an encycolpedia of greedy graphs.
We say a graph $G$ is tree-solvable if every configuration of size at least $\pi(G)$ has a solution in which the edges traversed by pebbling steps form an acyclic subgraph. The graph $H$ defined above is not tree-solvable. Indeed, the configuration $C(b,c,d,g,h)=(1,5,1,1,1)$ has no tree-solution for the root $f$. The configuration on $B_{3,3}$ above is not tree-solvable either, which shows that tree-solvability is also not always preserved by cartesian product. Another simple example is the cube $Q^3$: place $5$ pebbles at distance $3$ from the root $r$, and $1$ pebble at each of the three vertices at distance $2$ from $r$. Thus, not even greedy graphs are guaranteed to be tree-solvable.
Interestingly, the methods used in random pebbling suggest that almost all configurations above the pebbling threshold have greedy tree-solutions. Thus, it is reasonable to use a greedy algorithm to pare off most configurations, leaving possibly few configurations that require more sophisticated algorithms for solving.
E. Scheinerman and D. Ullman Fractional Graph Theory: A rational approach to the theory of graphs Wiley, New York (1997)G. Beightwell and E. Scheinerman Fractional dimension of partial orders Order 9 (1992), 139--158
