Solving Big Mazes in Small Space - A Monoid Labelling Approach

Solving Mazes - more formally, the graph reachability is a fundamental algorithmic problem in
space complexity: given a graph and two special vertices s and t, the task is to determine if there
is a path from s to t in the graph. While the directed reachability is complete for NL, the undirected
reachability is L-complete. The NL vs L question in space complexity theory is analogous to the P
vs NP in the time complexity domain.

A variant of the reachability problem, known as the Labelled Reachability problem for undirected
graphs where the edge labels are monoid elements is known to capture space-bounded complexity
classes L and NL. Given a labelled graph G(V, E) (labelled with ϕ : E → M ), s, t ∈ V and an
accepting subset F ⊆ M , the problem asks whether there is a walk P from s to t in G where
ϕ(P ) ∈ F . When the accepting element is also a part of the input, the problem has been studied
by Ramaswamy et al (2019) for the case when the monoid is aperiodic and when it is a group.

Motivated by the success of space-bounded algorithms for the graph reachability in the undirected
case, we study the labelled reachability when the accepting set is also fixed. We establish upper
and lower bounds for undirected labelled reachability over various monoids and accepting subsets,
which could potentially help us reach closer towards answering if L = NL. We give a logspace
algorithm for reachability over all monoids when the accepting set is the monoid identity and
show NL-hardness when the accepting element is a restricted idempotent. We also consider
arbitrary accepting subsets over commutative monoids and restricted union of groups monoid
to show logspace algorithms, and dichotomies for the building blocks of aperiodic monoids.