O'Reach: Even Faster Reachability in Large Graphs

DOI10.4230/LIPICS.SEA.2021.13arXiv2008.10932OpenAlexW3165168009MaRDI QIDQ6159900FDOQ6159900

Authors: Kathrin Hanauer, Christian Schulz 

Publication date: 23 June 2023

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/2008.10932

Recommendations

• Reachability in big graphs: a distributed indexing and querying approach
• Orienting graphs to optimize reachability
• Efficient graph reachability query answering using tree decomposition
• scientific article; zbMATH DE number 7650245
• scientific article; zbMATH DE number 7765385
• On the time-space complexity of reachability queries for preprocessed graphs
• Improved Dynamic Reachability Algorithms for Directed Graphs
• Space-efficient algorithms for reachability in directed geometric graphs

zbMATH Keywords

graph algorithmsreachabilityalgorithm engineeringreachability indexstatic graphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited In (3)

• MaRDiGraS: Simplified Building of Reachability Graphs on Large Clusters
• Reachability in big graphs: a distributed indexing and querying approach
• O’Reach: Even Faster Reachability in Large Graphs

This page was built for publication: O'Reach: Even Faster Reachability in Large Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6159900)