2026-07-26T00:12:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17399 2024-03-06T10:59:39Z ddc:004 open_access

The DAG Visit Approach for Pebbling and I/O Lower Bounds Bilardi, Gianfranco De Stefani, Lorenzo Pebbling Directed Acyclic Graph Pebbling number I/O complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gianfranco Bilardi and Lorenzo De Stefani 2022 Is Part Of LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2022.7 urn:nbn:de:0030-drops-173999 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.7 eng https://creativecommons.org/licenses/by/4.0/legalcode