| Title | : | Solving Big Mazes in Small Space - A Monoid Labelling Approach |
| Speaker | : | Nagashri Krishnakumar (IIT Madras) |
| Details | : | Tue, Feb 24, 2026 4:00 PM, @ SSB 334 |
| Abstract | : | 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 word problem is a fundamental computational problem over a groupoid $(mathcal{A,ullet})$: given a word over the alphabet $mathcal{A}$, the task is to determine if the word evaluates to an element in $mathcal{A}$ w.r.t. the operation $ullet$. The word problem is undecidable even for finitely presented groups. A bridge between the Reachability and Word problem: 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 $phi: E o M$), $s,t in V$ and an accepting subset $F subseteq M$, the problem asks whether there is a walk $P$ from $s$ to $t$ in $G$ where $phi(P) in F$. When the accepting element is also a part of the input, the problem has been studied by Ramaswamy {em 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. 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. |