Space complexity of reachability testing in labelled graphs

Vidhya Ramaswamy, Jayalal Sarma, K. S. Sunil

Research output: Contribution to journalArticlepeer-review


Fix an algebraic structure (A,⁎). Given a graph G=(V,E) and the labelling function ϕ (ϕ:E→A) for the edges, two nodes s, t∈V, and a subset F⊆A, the A-REACH problem asks if there is a path p (need not be simple) from s to t whose yield (result of the operation in the ordered set of the labels of the edges constituting the path) is in F. On the complexity frontier of this problem, we show the following results. • When A is a group whose size is polynomially bounded in the size of the graph (hence equivalently presented as a multiplication table at the input), and the graph is undirected, the A-REACH problem is in L. Building on this, using a decomposition in [4], we show that, when A is a fixed quasi-group, and the graph is undirected, the A-REACH problem is in L. In a contrast, we show NL-hardness of the problem over bidirected graphs, when A is a matrix group over Q, or an aperiodic monoid. • As our main theorem, we prove a dichotomy for graphs labelled with fixed aperiodic monoids by showing that for every fixed aperiodic monoid A, A-REACH problem is either in L or is NL-complete. • We show that there exists a monoid M, such that the reachability problem in general DAGs can be reduced to A-REACH problem for planar non-bipartite DAGs labelled with M. In contrast, we show that if the planar DAGs that we obtain above are bipartite, the problem can be further reduced to reachability testing in planar DAGs and hence is in UL.

Original languageEnglish (US)
Pages (from-to)40-53
Number of pages14
JournalJournal of Computer and System Sciences
StatePublished - Nov 2019
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science
  • Applied Mathematics
  • Computer Networks and Communications
  • Computational Theory and Mathematics


  • Algebraic reachability
  • Dichotomy
  • Space complexity
  • Word problems


Dive into the research topics of 'Space complexity of reachability testing in labelled graphs'. Together they form a unique fingerprint.

Cite this