| Title | : | Reachability Testing in Monoid-labelled Undirected Graphs |
| Speaker | : | Nagashri K (IITM) |
| Details | : | Fri, 3 Oct, 2025 12:00 PM @ SSB 334 |
| Abstract: | : | The NL vs L question in space complexity theory is analogous to the P vs NP in the time complexity domain. 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. A variant of the problem, known as labelled reachability problem for undirected graphs where the edges are labelled with monoid elements (more generally other algebraic structures) is known to capture space bounded complexity classes L and NL. Given a labelled graph G(V,E) (labelled with phi : E to M), s,t in V and an accepting subset F subseteq M, the problem asks to test 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 et al (2019) for the case when monoid is aperiodic and the case when monoid is a group. Motivated by the success of space bounded algorithms graph reachability problem in the undirected case, we study the labelled reachability problem when the accepting set is also fixed. We settle complexities for undirected labelled reachability over various monoids with different accepting subsets of the monoid, by obtaining upper and lower bounds which could potentially help us reach closer towards answering if L = NL. We give logspace algorithms for reachability over certain classes of monoids when the accepting set is the monoid identity. On the other hand, we obtain NL-hardness, when the accepting element is idempotent. We further expand our horizon to arbitrary accepting subsets. A key result is a logspace algorithm for a fixed monoid called mathcal{L}-(mathcal{R}-) commutative union of groups monoid, with any accepting subset of the monoid. In addition, we give a logspace algorithm for a restricted case of union of groups monoids with specific conditions over the accepting subset. Finally, we also show a dichotomy theorem for monoids which are building blocks of aperiodic monoids, with arbitrary accepting subsets of the monoid. |
