The DAG Visit Approach for Pebbling and I/O Lower Bounds

We introduce the notion of an r-visit of a Directed Acyclic Graph DAG G = (V,E), a sequence of the vertices of the DAG complying with a given rule r. A rule r specifies for each vertex v ∈ V a family of r-enabling sets of (immediate) predecessors: before visiting v, at least one of its enabling sets must have been visited. Special cases are the r(top)-rule (or, topological rule), for which the only enabling set is the set of all predecessors and the r(sin)-rule (or, singleton rule), for which the enabling sets are the singletons containing exactly one predecessor. The r-boundary complexity of a DAG G, br (G), is the minimum integer b such that there is an r-visit where, at each stage, for at most b of the vertices yet to be visited an enabling set has already been visited. By a reformulation of known results, it is shown that the boundary complexity of a DAG G is a lower bound to the pebbling number of the reverse DAG, GR. Several known pebbling lower bounds can be cast in terms of the...