Bilardi, Gianfranco ;
De Stefani, Lorenzo
The DAG Visit Approach for Pebbling and I/O Lower Bounds
Abstract
We introduce the notion of an rvisit 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 renabling 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 rboundary complexity of a DAG G, b_r(G), is the minimum integer b such that there is an rvisit 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, G^R. Several known pebbling lower bounds can be cast in terms of the r^{(sin)}boundary complexity. The main contributions of this paper are as follows:
 An existentially tight 𝒪(√{d_{out} n}) upper bound to the r^(sin)boundary complexity of any DAG of n vertices and outdegree d_{out}.
 An existentially tight 𝒪(d_{out}/(log₂ d_{out}) log₂ n) upper bound to the r^(top)boundary complexity of any DAG. (There are DAGs for which r^(top) provides a tight pebbling lower bound, whereas r^(sin) does not.)
 A visit partition technique for I/O lower bounds, which generalizes the Spartition I/O technique introduced by Hong and Kung in their classic paper "I/O complexity: The RedBlue pebble game". The visit partition approach yields tight I/O bounds for some DAGs for which the Spartition technique can only yield a trivial lower bound.
BibTeX  Entry
@InProceedings{bilardi_et_al:LIPIcs.FSTTCS.2022.7,
author = {Bilardi, Gianfranco and De Stefani, Lorenzo},
title = {{The DAG Visit Approach for Pebbling and I/O Lower Bounds}},
booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
pages = {7:17:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772617},
ISSN = {18688969},
year = {2022},
volume = {250},
editor = {Dawar, Anuj and Guruswami, Venkatesan},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17399},
URN = {urn:nbn:de:0030drops173999},
doi = {10.4230/LIPIcs.FSTTCS.2022.7},
annote = {Keywords: Pebbling, Directed Acyclic Graph, Pebbling number, I/O complexity}
}
14.12.2022
Keywords: 

Pebbling, Directed Acyclic Graph, Pebbling number, I/O complexity 
Seminar: 

42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Issue date: 

2022 
Date of publication: 

14.12.2022 