| Title | : | Space Complexity of Algebraic Reachability : a Dichotomy Theorem |
| Speaker | : | Sunil.K.S (IITM) |
| Details | : | Fri, 9 Dec, 2016 2:00 PM @ BSB 361 |
| Abstract: | : | Reachability problems in mathematical structures is a well-studied problem in space complexity. An important example is the graph reachability problem where given a graph G and two special vertices s and t, is there a path from s to t in G. The famous NL vs L problem can be equivalently restated as the challenge of designing a deterministic logspace(L) algorithm for reachability problem. Restricted versions of this problem falls in natural sub-classes of nondeterministic logspace(NL). For example, reachability for planar graphs is in unambiguous logspace(UL - Reinheardt, Allender 2000). In a breakthrough result, Reingold (2005) showed that the reachability problem for undirected graphs is in deterministic logspace. A natural extension of the reachability problem using algebraic structure is the A-Reach problem : fix an algebraic structure A with a binary operation *. Given a graph whose edges are labelled with the elements of A, a subset F ⊆ A and two special vertices s and t: 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. The driving question in this work is: Can we reduce directed graph reachability to undirected labelled reachability over carefully chosen algebraic structures?. This motivates the study of space complexity of algebraic reachability for different algebraic structures. When we use any fixed monoid as the underlying algebraic stucture, the A-reach problem over undirected graphs is NL-complete. In fact, the monoid used is even aperiodic. Following this, we prove a dichotomy theorem based on the type of the aperiodic monoid. More precisely, we show that for every fixed aperiodic monoid A, A-Reach problem is either in L or is NL-complete. For more structured labelling sets - when A is a group whose size is polynomially bounded in the size of the graph or when A is a fixed quasi-group, and the graph is undirected, A-Reach problem is in L. When A is a matrix group over Q, we show the NL-hardness of the problem over bidirected graphs. We also show that there exists an aperiodic 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 DAG that we obtain above is bipartite, the problem can be further reduced to reachability testing in planar DAGs and hence is in unambiguous logspace. |
