Optimal reachability and a space time tradeoff for distance queries in constant treewidth graphs Conference Paper


Author(s): Chatterjee, Krishnendu; Ibsen-Jensen, Rasmus; Pavlogiannis, Andreas
Title: Optimal reachability and a space time tradeoff for distance queries in constant treewidth graphs
Title Series: LIPIcs
Affiliation IST Austria
Abstract: We consider data-structures for answering reachability and distance queries on constant-treewidth graphs with n nodes, on the standard RAM computational model with wordsize W=Theta(log n). Our first contribution is a data-structure that after O(n) preprocessing time, allows (1) pair reachability queries in O(1) time; and (2) single-source reachability queries in O(n/log n) time. This is (asymptotically) optimal and is faster than DFS/BFS when answering more than a constant number of single-source queries. The data-structure uses at all times O(n) space. Our second contribution is a space-time tradeoff data-structure for distance queries. For any epsilon in [1/2,1], we provide a data-structure with polynomial preprocessing time that allows pair queries in O(n^{1-\epsilon} alpha(n)) time, where alpha is the inverse of the Ackermann function, and at all times uses O(n^epsilon) space. The input graph G is not considered in the space complexity.
Keywords: Graph algorithms; Constant-treewidth graphs; reachability queries; distance queries
Conference Title: ESA: European Symposium on Algorithms
Volume: 57
Conference Dates: August 22-26, 2016
Conference Location: Aarhus, DK
ISBN: 9783662483497
Publisher: Springer  
Date Published: 2016-01-01
Start Page: Article number: 28
Copyright Statement: CC BY
Sponsor: The research was partly supported by Austrian Science Fund (FWF) Grant No P23499-N23, FWF NFN Grant No S11407-N23 (RiSE/SHiNE) and ERC Start grant (279307: Graph Games).
URL:
DOI: 10.4230/LIPIcs.ESA.2016.28
Open access: yes (OA journal)