Chakraborty, Sankardeep ;
Mukherjee, Anish ;
Raman, Venkatesh ;
Satti, Srinivasa Rao
A Framework for Inplace Graph Algorithms
Abstract
Readonly memory (ROM) model is a classical model of computation to study timespace tradeoffs of algorithms. A classical result on the ROM model is that any algorithm to sort n numbers using O(s) words of extra space requires Omega (n^2/s) comparisons for lg n <= s <= n/lg n and the bound has also been recently matched by an algorithm. However, if we relax the model, we do have sorting algorithms (say Heapsort) that can sort using O(n lg n) comparisons using O(lg n) bits of extra space, even keeping a permutation of the given input sequence at anytime during the algorithm.
We address similar relaxations for graph algorithms. We show that a simple natural relaxation of ROM model allows us to implement fundamental graph search methods like BFS and DFS more space efficiently than in ROM. By simply allowing elements in the adjacency list of a vertex to be permuted, we show that, on an undirected or directed connected graph G having n vertices and m edges, the vertices of G can be output in a DFS or BFS order using O(lg n) bits of extra space and O(n^3 lg n) time. Thus we obtain similar bounds for reachability and shortest path distance (both for undirected and directed graphs). With a little more (but still polynomial) time, we can also output vertices in the lexDFS order. As reachability in directed graphs (even in DAGs) and shortest path distance (even in undirected graphs) are NLcomplete, and lexDFS is Pcomplete, our results show that our model is more powerful than ROM if L != P.
En route, we also introduce and develop algorithms for another relaxation of ROM where the adjacency lists of the vertices are circular lists and we can modify only the heads of the lists. Here we first show a linear time DFS implementation using n + O(lg n) bits of extra space. Improving the extra space exponentially to only O(lg n) bits, we also obtain BFS and DFS albeit with a slightly slower running time. Both the models we propose maintain the graph structure throughout the algorithm, only the order of vertices in the adjacency list changes. In sharp contrast, for BFS and DFS, to the best of our knowledge, there are no algorithms in ROM that use even O(n^{1epsilon}) bits of extra space; in fact, implementing DFS using cn bits for c<1 has been mentioned as an open problem. Furthermore, DFS (BFS, respectively) algorithms using n+o(n) (o(n), respectively) bits of extra use Reingold's [JACM, 2008] or Barnes et al's reachability algorithm [SICOMP, 1998] and hence have high runtime. Our results can be contrasted with the recent result of Buhrman et al. [STOC, 2014] which gives an algorithm for directed streachability on catalytic Turing machines using O(lg n) bits with catalytic space O(n^2 lg n) and time O(n^9).
BibTeX  Entry
@InProceedings{chakraborty_et_al:LIPIcs:2018:9476,
author = {Sankardeep Chakraborty and Anish Mukherjee and Venkatesh Raman and Srinivasa Rao Satti},
title = {{A Framework for Inplace Graph Algorithms}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {13:113:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770811},
ISSN = {18688969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9476},
URN = {urn:nbn:de:0030drops94760},
doi = {10.4230/LIPIcs.ESA.2018.13},
annote = {Keywords: DFS, BFS, inplace algorithm, spaceefficient graph algorithms, logspace}
}
2018
Keywords: 

DFS, BFS, inplace algorithm, spaceefficient graph algorithms, logspace 
Seminar: 

26th Annual European Symposium on Algorithms (ESA 2018)

Issue date: 

2018 
Date of publication: 

2018 