I/O-efficient algorithms for graphs of bounded treewidth
Anil Maheshwari, Norbert Zeh · 2001
We present an algorithm that takes O(sort(N)) I/Os 1 to compute a tree decomposition of width at most k, for any graph G of treewidth at most k and size N. Given such a tree decomposition, we use a dynamic programming framework to solve a wide variety of problems on G in O(N/(DB)) I/Os, including the single-source shortest path problem and a number of problems that are NP-hard on general graphs. The tree decomposition can also be used to obtain an optimal separator decomposition of G. We use such a decomposition to perform depth-first search in G in O(N/(DB)) I/Os. As important tools that are used in the tree decomposition algorithm, we introduce flippable DAGs and present an algorithm that computes a perfect elimination ordering of a k-tree in O(sort(N)) I/Os. The second contribution of our paper, which is of independent interest, is a general and simple framework for obtaining I/O-efficient algorithms for a number of graph problems that can be solved using greedy algorithms in internal memory. We apply this framework in order to obtain an improved algorithm for finding a maximal matching and the first deterministic I/Oefficient algorithm for finding a maximal independent set of an arbitrary graph. Both algorithms take O(sort(|V |+|E|)) I/Os. The maximal matching algorithm is used in the tree decomposition algorithm.