Space efficient graph algorithms [HBNI Th 134]

Abstract

Due to the rapid growth of data, algorithms that utilize the space efficiently are increasingly becoming important. This thesis focusses on an emerging area of designing algorithms for fundamental graph problems using little space without compromising on the speed as well. We provide such algorithms for various graph search methods (depth-first search, breadth-first search, maximum cardinality search) and fundamental connectivity prob- lems (biconnectivity, 2-edge connectivity and strong connectivity) in the read-only memory model using O(n) bits of extra space. Most of these results require techniques from succinct data structures along with suitable modifications of the existing graph algorithms. We also provide sub-linear bits algorithms for various optimization problems on bounded treewidth graphs in the read-only memory model. In fact, we prove the following more general meta theorem which says, for bounded treewidth graphs, if any graph problem can be described in monadic second order (MSO) logic, we can obtain a smooth deterministic time-space trade-off from logarithmic words to linear space. Furthermore, we introduce two new frameworks for designing efficient in-place graph algorithms (where the input elements can be moved around in a restricted way) and obtain such algorithms for several basic algorithmic graph problems. In particular, we develop algorithms for depth-first search and breadth-first search in these models taking only O (log n) extra bits albeit taking super-linear time. In sharp contrast, we do not know of any algorithms for these problems taking sub-linear bits of space in the read-only memory model