ECCC-Report TR15-016https://eccc.weizmann.ac.il/report/2015/016Comments and Revisions published for TR15-016en-usMon, 27 Apr 2015 14:48:06 +0300
Revision 1
| An $O(n^{\epsilon})$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs |
Diptarka Chakraborty,
Raghunath Tewari
https://eccc.weizmann.ac.il/report/2015/016#revision1Given a graph $G$ and two vertices $s$ and $t$ in it, {\em graph reachability} is the problem of checking whether there exists a path from $s$ to $t$ in $G$. We show that reachability in directed layered planar graphs can be decided in polynomial time and $O(n^\epsilon)$ space, for any $\epsilon > 0$. The previous best known space bound for this problem with polynomial time was approximately $O(\sqrt{n})$ space \cite{INPVW13}.
Deciding graph reachability in {\SC} is an important open question in complexity theory and in this paper we make progress towards resolving this question.Mon, 27 Apr 2015 14:48:06 +0300https://eccc.weizmann.ac.il/report/2015/016#revision1
Paper TR15-016
| An $O(n^{\epsilon})$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs |
Diptarka Chakraborty,
Raghunath Tewari
https://eccc.weizmann.ac.il/report/2015/016Given a graph $G$ and two vertices $s$ and $t$ in it, {\em graph reachability} is the problem of checking whether there exists a path from $s$ to $t$ in $G$. We show that reachability in directed layered planar graphs can be decided in polynomial time and $O(n^\epsilon)$ space, for any $\epsilon > 0$. The previous best known space bound for this problem with polynomial time was approximately $O(\sqrt{n})$ space \cite{INPVW13}.
Deciding graph reachability in {\SC} is an important open question in complexity theory and in this paper we make progress towards resolving this question.Sat, 31 Jan 2015 15:59:56 +0200https://eccc.weizmann.ac.il/report/2015/016