| Title | : | Towards Making Space-bounded Non-Determinism Unambiguous |
| Speaker | : | Anant Dhayal (IITM) |
| Details | : | Tue, 24 Feb, 2015 4:00 PM @ BSB 361 |
| Abstract: | : | For a graph $G(V,E)$ and a vertex $s in V$, a weighting scheme ($w : E to mathbb{N}$) is called a {em min-unique} weighting scheme, if for any vertex $v$ of the graph $G$, there is a unique path of minimum weight from $s$ to $v$. Instead, if the number of paths of minimum weight is bounded by $n^c$ ($n = |V|$) for some constant $c$, then the weighting scheme is called a {em min-poly} weighting scheme. Weight of a path $p$ is the sum of the weights of the edges appearing in $p$.
In this work, we propose an unambiguous non-deterministic log-space ($UL$) algorithm for the problem of testing reachability in layered directed acyclic graphs (DAGs) augmented with a {em min-poly} weighting scheme. This improves the result due to (Allender and Reinhardt 2000) where a $UL$ algorithm was given for the case when the weighting scheme is {em min-unique}. Our main technique is a triple inductive counting, which generalizes the techniques of (Immerman, Szelepcinyi 1988) and (Allender, Reinhardt 2000), combined with a hashing technique due to (Fredman, Komlos, Szemeredi 1984). We combine this with a complementary unambiguous verification method, to give the desired $UL$ algorithm. Our result implies, that it suffices to design log-space computable {em min-poly} weighting schemes for graphs, in order to make space bounded non-determinism unambiguous in general. On a different frontier, while the reachability for planar graphs was shown to be in $UL$ using {em min-unique} weighting scheme technique, a logspace algorithm for the problem is still elusive. We will present a different approach towards the problem by ``planarizing" a known (Toran 2000) reduction from graph reachability problem to Graph Isomorphism problem (noting that Planar Graph Isomorphism problem was shown recently to be in log-space - by Datta, Limaye, Nimbhorkar, Thierauf, Wagner, 2009). We present negative results about the approach. |
