# A Greedy Approach to Answer Reachability Queries on DAGs

arXiv: https://arxiv.org/abs/1611.02506 · HTML: https://mlsanity.com/paper/1611.02506/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2016.

## Built on by (most cited first, 1 of 1)

- [ZK-HybridFL: Zero-Knowledge Proof-Enhanced Hybrid Ledger for Federated Learning](https://mlsanity.com/paper/2601.22302/) (2026)

## Abstract (arXiv)

Several modern applications involve huge graphs and require fast answers to reachability queries. In more than two decades since first proposals, several approaches have been presented adopting on-line searches, hop labelling or transitive closure compression. Transitive closure compression techniques usually construct a graph reachability index, for example by decomposing the graph into disjoint chains. As memory consumption is proportional to the number of chains, the target of those algorithms is to decompose the graph into an optimal number width of chains. However, commonly used techniques fail to meet general expectations, are exceedingly complex, and their application on large graphs is impractical. The main contribution of this paper is a novel approach to construct such reachability indexes. The proposed method decomposes the graph into a sub-optimal number widehatc of chains by following a greedy strategy. We show that, given a vertex topological order, such a decomposition is obtained in O(widehatc m) time, and requires O(widehatc n) space, with widehatc bounded by [c log(fracnc)]. We provide experimental evidence suggesting that, on different categories of automatically generated benchmarks as well as on graphs arising from the field of logic synthesis and formal verification, the proposed method produces a number of chains very close to the optimum, while significantly reducing computation time.