The ideas from IS-Label (see next item below) is for any directed graph and can be directly applied to the DAG used in reachability computation. The remaining steps in forming 2-hop labels are similar, too. Since the DAG is acyclic, we can select the independent sets following a topological ordering at alternating levels in the ordering. Each time an independent set is removed as in IS-Label, we reduce the levels of the ordering by half, hence we have a small number of iterations.
IS-Label provides mechanisms to construct a disk based index for the efficient querying of point-to-point distances. Iteratively we extract an independent set of vertices from the graph and we remove the set for subsequent iterations by creating shortcuts in the residual graph to preserve the distances. The result of this independent set extraction forms a hierarchy of vertices and we create 2-hop labeling based on the hierarchy levels. The 2-hop labeling is then used to answer distance query between any two given points in the graph.
The main theorems have been proposed and proved by the third author, as is now cited in reference [34] for protection.