6
$\begingroup$

Out of curiosity, I tried finding the original paper showing that there are graphs that require $n/\log n$ pebbles in the sense of Hopcroft, Paul, and Valiant’s seminal paper “On Time Versus Space”. (Which you can access here: http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/p332-hopcroft.pdf).

Sadly, this result is cited as “personal communication,” and any other lower bounds I could find use the different definition of pebbling in graph theory. Does anyone know where I could find a construction of a graph requiring $n/\log n$ pebbles?

$\endgroup$
8
$\begingroup$

A full proof (based on superconcentrators) can be found in chapter 24 "The pebble game" of the book

Uwe Schöning and Randall Pruim:
Gems of Theoretical Computer Science
Springer, 1998

ISBN 978-3-642-64352-1
https://link.springer.com/book/10.1007%2F978-3-642-60322-8

$\endgroup$
  • 2
    $\begingroup$ As this answers my question, I will accept this answer. However, it would be nice to see a different source for those who don’t want to spend $30. $\endgroup$ – exfret Aug 28 at 14:04
  • $\begingroup$ Looks like the publishers of the book are fans of SETCS, they just raised the price to $109.00 ouch ! :-) $\endgroup$ – William Hird Sep 1 at 5:20
  • $\begingroup$ @WilliamHird I think that was the case before. I was referring to the price of the specific chapter referenced in the answer. That being said, someone wanting context for said chapter would indeed have to cough up the whole price! $\endgroup$ – exfret Sep 3 at 17:18
  • 1
    $\begingroup$ Also, for those whose universities don't subscribe to Springer and who don't wish to spend the money, I would recommend looking up "expander graphs". These seem to be canonical examples of "hard to pebble" graphs. $\endgroup$ – exfret Sep 3 at 17:20
5
$\begingroup$

Not sure whether I am missing something, but...

The Omega(n/log n) lower bound is from:

[PTC77] Wolfgang J. Paul, Robert Endre Tarjan, and James R. Celoni. Space bounds for a game on graphs. Mathematical Systems Theory, 10:239–251, 1977.

There is a strengthening of this to a non-deterministic version of the pebble game (so-called black-white pebbling) in:

[GT78] John R. Gilbert and Robert Endre Tarjan. Variations of a pebble game on graphs. Technical Report STAN-CS-78-661, Stanford University, 1978. Available at http://infolab.stanford.edu/TR/CS-TR-78-661.html .

And --- self-plug warning --- you find a somewhat careful exposition of the latter lower bound, together with some nice illustrations, in the survey http://www.csc.kth.se/~jakobn/research/PebblingSurveyTMP.pdf (see Section 7 starting on page 51).

Another good source on some classic pebbling stuff is Chapter 10 of:

[Sav98] John E. Savage. Models of Computation: Exploring the Power of Computing. Addison-Wesley,1998. Available at http://www.modelsofcomputation.org .

$\endgroup$
  • $\begingroup$ This is so perfect! Thank you! $\endgroup$ – exfret Sep 4 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.