Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR15-016 | 27th April 2015 14:48

#### An $O(n^{\epsilon})$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs

Revision #1
Authors: Diptarka Chakraborty, Raghunath Tewari
Accepted on: 27th April 2015 14:48
Keywords:

Abstract:

Given 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.

### Paper:

TR15-016 | 16th January 2015 07:35

#### An $O(n^{\epsilon})$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs

TR15-016
Authors: Diptarka Chakraborty, Raghunath Tewari
Publication: 31st January 2015 15:59
Given 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}.