A universal bound on the space complexity of Directed Acyclic Graph computations

It is shown that $S(G)=O(m\mathrm{/}{\log }_{2}m+d)$ pebbles are sufficient to pebble any DAG $G=(V,E)$, with $m$ edges and maximum in-degree $d$. It was previously known that $S(G)=O(dn\mathrm{/}\log n)$. The result builds on two novel ideas. The first is the notion of $B-budgetdecomposition$ of a DAG $G$, an efficiently computable partition of $G$ into at most $2^{\lfloor \frac{m}{B}\rfloor }$ sub-DAGs, whose cumulative space requirement is at most $B$. The second is the challenging vertices technique, which constructs a pebbling schedule for $G$ from a pebbling schedule for a simplified DAG $G^{\mathrm{\prime }}$, obtained by removing from $G$ a selected set of vertices $W$ and their incident edges. This technique also yields improved pebbling upper bounds for DAGs with bounded genus and for DAGs with bounded topological depth.