Parameterized Linear Time Transitive Closure

Abstract

In this paper, we first study the problem of decomposing a directed acyclic graph (DAG), $G=(V, E)$ into vertex-disjoint chains and present a fast and practical chain decomposition technique. Our algorithm produces results that are very close to the optimum. The availability of fast and practical chain decomposition algorithms opens the way for novel solutions to fundamental problems. Building on our chain decomposition method, we present fast and practical techniques for computing the reachability information in a directed graph (i.e., its transitive closure). We focus on applicable solutions that enable constant-time reachability queries. Given any path/chain decomposition of $G$, our technique computes a reachability indexing scheme of a DAG, $G=(V, E)$ in parameterized linear time.

The experimental results reveal that our method is very fast in practice, indicating that chain decomposition algorithms can be applied to obtain fast and practical solutions to the transitive closure (TC) problem.
Furthermore, we show that we can find a substantially large subset of the transitive edges of $G$ in linear time using any chain decomposition. Our extensive experimental results show the interplay between these concepts in various models of DAGs. Additionally, we show the efficiency of this solution by speeding up Fulkerson's method for finding the minimum chain decomposition that corresponds exactly to the width of the graph.