[proofplan] We define a bounded reachability predicate $\operatorname{Reach}_G(x,y,\ell)$, meaning that $y$ is reachable from $x$ by a directed path of length at most $\ell$. The recursive algorithm tests this predicate by splitting a path of length at most $\ell$ through a midpoint and trying all possible midpoint vertices. Correctness follows by induction on $\ell$, and the space bound follows because the recursion depth is logarithmic while each stack frame stores only constantly many vertices, counters, and length parameters of size $O(\log N)$. [/proofplan]

[step:Define the bounded reachability predicate and recursive algorithm]For vertices $x,y\in V$ and an integer $\ell\in\{0,1,\dots,N-1\}$, define the predicate $\operatorname{Reach}_G(x,y,\ell)$ to mean that there exists a directed path in $G$ from $x$ to $y$ using at most $\ell$ directed edges. We define a deterministic recursive procedure \begin{align*} R_G: V\times V\times \{0,1,\dots,N-1\}\to \{\mathrm{true},\mathrm{false}\} \end{align*} as follows. If $\ell=0$, the procedure returns $\mathrm{true}$ exactly when $x=y$. If $\ell=1$, the procedure returns $\mathrm{true}$ exactly when either $x=y$ or the adjacency procedure accepts the pair $(x,y)$, meaning $(x,y)\in E$. If $\ell\ge 2$, the procedure enumerates every vertex $u\in V$. For each such $u$, it recursively computes \begin{align*} R_G(x,u,\lceil \ell/2\rceil) \end{align*} and, if this value is $\mathrm{true}$, recursively computes \begin{align*} R_G(u,y,\lfloor \ell/2\rfloor). \end{align*} The procedure returns $\mathrm{true}$ if for some enumerated $u\in V$ both recursive calls return $\mathrm{true}$; otherwise it returns $\mathrm{false}$ after all vertices have been tested.[/step]

[guided]The purpose of the auxiliary parameter $\ell$ is to separate ordinary reachability from bounded reachability. We define $\operatorname{Reach}_G(x,y,\ell)$ to mean that there is a directed path from $x$ to $y$ using at most $\ell$ edges. This bounded version is what makes the divide-and-conquer recursion possible. The recursive procedure \begin{align*} R_G: V\times V\times \{0,1,\dots,N-1\}\to \{\mathrm{true},\mathrm{false}\} \end{align*} is defined by cases on $\ell$. When $\ell=0$, a path with at most zero edges exists from $x$ to $y$ exactly when $x=y$, so the procedure returns $\mathrm{true}$ precisely in that case. When $\ell=1$, a path with at most one edge exists exactly when either $x=y$ or there is a directed edge from $x$ to $y$. Thus the procedure tests whether $x=y$, and if not, calls the given deterministic adjacency procedure on the ordered pair $(x,y)$. By hypothesis, that adjacency procedure decides whether $(x,y)\in E$ using $A(N)$ additional workspace. For $\ell\ge 2$, the idea is that any path of length at most $\ell$ has a midpoint after at most $\lceil \ell/2\rceil$ edges. We therefore enumerate all possible midpoint vertices $u\in V$ and test whether $u$ is reachable from $x$ within $\lceil \ell/2\rceil$ edges and whether $y$ is reachable from $u$ within $\lfloor \ell/2\rfloor$ edges. Formally, for each enumerated $u\in V$, the procedure computes \begin{align*} R_G(x,u,\lceil \ell/2\rceil) \end{align*} and, if this value is $\mathrm{true}$, computes \begin{align*} R_G(u,y,\lfloor \ell/2\rfloor). \end{align*} It accepts exactly when both recursive calls accept for at least one midpoint $u$.[/guided]

[step:Prove the recursive procedure decides bounded reachability] We prove by induction on $\ell\in\{0,1,\dots,N-1\}$ that, for all $x,y\in V$, \begin{align*} R_G(x,y,\ell)=\mathrm{true}\quad\Longleftrightarrow\quad \operatorname{Reach}_G(x,y,\ell). \end{align*} For $\ell=0$, a directed path of length at most $0$ from $x$ to $y$ exists exactly when $x=y$, which is exactly the condition tested by $R_G$. For $\ell=1$, a directed path of length at most $1$ from $x$ to $y$ exists exactly when either $x=y$ or $(x,y)\in E$. This is exactly the condition tested by $R_G$ using the adjacency procedure. Assume now that $\ell\ge 2$ and that the equivalence holds for all smaller length bounds. First suppose that $R_G(x,y,\ell)=\mathrm{true}$. Then there exists $u\in V$ such that \begin{align*} R_G(x,u,\lceil \ell/2\rceil)=\mathrm{true} \end{align*} and \begin{align*} R_G(u,y,\lfloor \ell/2\rfloor)=\mathrm{true}. \end{align*} Because $\lceil \ell/2\rceil<\ell$ and $\lfloor \ell/2\rfloor<\ell$, the induction hypothesis gives a path from $x$ to $u$ of length at most $\lceil \ell/2\rceil$ and a path from $u$ to $y$ of length at most $\lfloor \ell/2\rfloor$. Concatenating these two directed paths gives a directed path from $x$ to $y$ of length at most \begin{align*} \lceil \ell/2\rceil+\lfloor \ell/2\rfloor=\ell. \end{align*} Thus $\operatorname{Reach}_G(x,y,\ell)$ holds. Conversely, suppose $\operatorname{Reach}_G(x,y,\ell)$ holds. Choose a directed path \begin{align*} x=v_0,\ v_1,\ \dots,\ v_m=y \end{align*} with $0\le m\le \ell$. Define \begin{align*} r=\min\{m,\lceil \ell/2\rceil\} \end{align*} and set $u=v_r$. The initial segment from $x$ to $u$ has length $r\le \lceil \ell/2\rceil$. If $m\le \lceil \ell/2\rceil$, then the terminal segment from $u=y$ to $y$ has length $0\le \lfloor \ell/2\rfloor$. If $m>\lceil \ell/2\rceil$, then $r=\lceil \ell/2\rceil$, and the terminal segment has length \begin{align*} m-r\le \ell-\lceil \ell/2\rceil=\lfloor \ell/2\rfloor. \end{align*} In either case, \begin{align*} \operatorname{Reach}_G(x,u,\lceil \ell/2\rceil) \end{align*} and \begin{align*} \operatorname{Reach}_G(u,y,\lfloor \ell/2\rfloor) \end{align*} hold. By the induction hypothesis, both corresponding recursive calls return $\mathrm{true}$. Since $R_G$ enumerates every vertex of $V$, it eventually tests this midpoint $u$ and returns $\mathrm{true}$. This proves the induction. [/step]

[step:Reduce ordinary reachability to bounded reachability with length $N-1$] If $b$ is reachable from $a$, then there is a directed path from $a$ to $b$. Among all such paths choose one of minimal length. This path has no repeated vertex: if a vertex repeated, the closed subpath between the two occurrences could be removed, producing a shorter directed path with the same endpoints. Hence the path uses at most $N$ vertices and therefore at most $N-1$ edges. Thus $b$ is reachable from $a$ if and only if $\operatorname{Reach}_G(a,b,N-1)$ holds. By the previous step, the procedure $R_G(a,b,N-1)$ decides ordinary reachability from $a$ to $b$. [/step]

[step:Bound the recursion depth and the storage per stack frame] Along every recursive branch, the length parameter $\ell$ is replaced by either $\lceil \ell/2\rceil$ or $\lfloor \ell/2\rfloor$. Starting from $\ell=N-1$, after $d$ recursive levels the length parameter is at most $\lceil (N-1)/2^d\rceil$. Therefore the recursion reaches a base case after $O(\log N)$ levels. At each recursive level, the procedure stores only a constant number of vertices and integer parameters: the current endpoints $x,y\in V$, the current midpoint $u\in V$, the current length bound $\ell$, and the state of the enumeration over $V$. By hypothesis, each vertex requires $O(\log N)$ bits, and the integer parameters range over sets of size at most $N$, so they also require $O(\log N)$ bits. Hence each stack frame uses $O(\log N)$ workspace. Multiplying the $O(\log N)$ stack frames by $O(\log N)$ bits per frame gives \begin{align*} O((\log N)^2) \end{align*} workspace for the recursion stack. [/step]

[step:Add the adjacency workspace and conclude the reachability space bound] The only non-recursive subroutine requiring more than the stack-frame storage is the adjacency procedure used in the base case $\ell=1$. By hypothesis, this procedure uses $A(N)$ additional workspace. Since the algorithm evaluates recursive calls sequentially, the workspace for adjacency testing is reused rather than accumulated across different branches of the recursion tree. Therefore the total deterministic workspace used by the algorithm is \begin{align*} O((\log N)^2 + A(N)). \end{align*} By applying the procedure to $(a,b,N-1)$, the algorithm decides whether $b$ is reachable from $a$ within the claimed space bound. [/step]