  One of the most fundamental problems in computer science is the reachability
problem: Given a directed graph and two vertices s and t, can s reach t via a
path? We revisit existing techniques and combine them with new approaches to
support a large portion of reachability queries in constant time using a
linear-sized reachability index. Our new algorithm O'Reach can be easily
combined with previously developed solutions for the problem or run standalone.
  In a detailed experimental study, we compare a variety of algorithms with
respect to their index-building and query times as well as their memory
footprint on a diverse set of instances. Our experiments indicate that the
query performance often depends strongly not only on the type of graph, but
also on the result, i.e., reachable or unreachable. Furthermore, we show that
previous algorithms are significantly sped up when combined with our new
approach in almost all scenarios. Surprisingly, due to cache effects, a higher
investment in space doesn't necessarily pay off: Reachability queries can often
be answered even faster than single memory accesses in a precomputed full
reachability matrix.
