License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2022.7
URN: urn:nbn:de:0030-drops-173999
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17399/
Bilardi, Gianfranco ;
De Stefani, Lorenzo
The DAG Visit Approach for Pebbling and I/O Lower Bounds
Abstract
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, b_r(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, 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 out-degree 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 S-partition I/O technique introduced by Hong and Kung in their classic paper "I/O complexity: The Red-Blue pebble game". The visit partition approach yields tight I/O bounds for some DAGs for which the S-partition 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:1--7:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-261-7},
ISSN = {1868-8969},
year = {2022},
volume = {250},
editor = {Dawar, Anuj and Guruswami, Venkatesan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17399},
URN = {urn:nbn:de:0030-drops-173999},
doi = {10.4230/LIPIcs.FSTTCS.2022.7},
annote = {Keywords: Pebbling, Directed Acyclic Graph, Pebbling number, I/O complexity}
}
|
Keywords: |
|
Pebbling, Directed Acyclic Graph, Pebbling number, I/O complexity |
|
Collection: |
|
42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
14.12.2022 |
