Concise Theoretical and Algorithmic Notes on Reachability Queries in Multilayer Graphs

Multilayer graphs are particularly useful in complex systems, when multiple types of interactions exist among entities. Despite the growing use of multilayer graphs in modeling complex environments and the foundational role of reachability in planning and decision-making, there is limited work on reachability queries in multilayer settings, particularly those relevant to reinforcement learning agents. This work addresses the gap by proposing an algorithmic approach that integrates multilayer graph structure with classical reachability tools. In this work, we investigate graph reachability on a multilayer graph and propose a linear-time reachability algorithm 1 that checks path existence from a designated start node to a target node, while remaining applicable to arbitrary node pairs. The algorithm combines two techniques: computing the strongly connected components of the multilayer graph and performing a reverse depth-first search traversal.