TY - GEN
T1 - Space complexity of reachability testing in labelled graphs
AU - Ramaswamy, Vidhya
AU - Sarma, Jayalal
AU - Sunil, K. S.
N1 - Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - 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 contrast, we show NL-hardness of the problem over bidirected graphs, when A is a matrix group over ℚ. When A is a fixed aperiodic monoid, we show that the problem is NL-complete. – 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.
AB - 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 contrast, we show NL-hardness of the problem over bidirected graphs, when A is a matrix group over ℚ. When A is a fixed aperiodic monoid, we show that the problem is NL-complete. – 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.
UR - http://www.scopus.com/inward/record.url?scp=85013436848&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85013436848&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-53733-7_26
DO - 10.1007/978-3-319-53733-7_26
M3 - Conference contribution
AN - SCOPUS:85013436848
SN - 9783319537320
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 351
EP - 363
BT - Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings
A2 - Drewes, Frank
A2 - Martín-Vide, Carlos
A2 - Truthe, Bianca
PB - Springer Verlag
T2 - 11th International Conference on Language and Automata Theory and Applications, LATA 2017
Y2 - 6 March 2017 through 9 March 2017
ER -