= Solution
The printed question calls the route a <path in a graph> and writes $p\subseteq E(G)$, without specifying whether repeated <vertices> are allowed.<Computational Complexity examination paper of the University of Oxford (2015)>[Printed p. 4, Question 3(e)]{ref} Use the computational reachability convention that a permitted route is a directed <walk>: repeated <vertices> are allowed and length counts traversed <edges> with multiplicity. This matters for the <integer parity> restriction, because deleting a closed portion of odd length can change the <integer parity>. The proof below establishes the stated <NL>-completeness for this convention; it does not establish that claim for a simple <path in a graph>.
For membership of <even-length directed reachability> in <NL>, form the conceptual parity <graph> with <vertex set>
$$
V(G)\times\{0,1\}
$$
and directed <edges>
$$
(u,b)\longrightarrow(w,1-b)
\quad\Longleftrightarrow\quad (u,w)\in E(G).
$$
After a directed <walk> of length $j$ from $(v,0)$, the second coordinate equals $j\bmod2$. Therefore there is an even-length directed <walk> from $v$ to $v'$ in $G$ exactly when $(v',0)$ is reachable from $(v,0)$ in this parity <graph>. It has $2N$ <vertices>. Guess successive <edges> while storing the original current <vertex>, one <parity bit>, and a counter bounded by $2N-1$. If the target pair is reachable, it has a simple <path in a graph> in this enlarged <graph> of at most $2N-1$ <edges>. This is an <NL> procedure; the parity <graph> need not be materialized.
For <NL>-hardness, reduce directed reachability by subdividing each directed <edge> $(u,w)$ with its own new <vertex> $a_{uw}$:
$$
u\longrightarrow a_{uw}\longrightarrow w.
$$
Retain $v,v'$ as the endpoints and add no other <edges>. Every original directed <walk> of length $j$ becomes a directed <walk> of even length $2j$. Conversely, a directed <walk> between original <vertices> in the new <graph> must alternate original and subdivision <vertices>. Compressing each two-<edge> segment recovers a directed <walk> in $G$. Hence
$$
\langle G,v,v'\rangle\in\mathrm{Reachability}
\quad\Longleftrightarrow\quad
\langle G',v,v'\rangle\in\mathrm{E\text{-}Reachability}.
$$
A <logspace transducer> enumerates the original <edges>, labels each new <vertex> by its <edge> endpoints or its position in the <input>, and emits its two replacement <edges>. All labels and counters take $O(\log n)$ <bits>, and the output is of <polynomial> size. Thus this is a <logspace many-one reduction>, proving
$$
\boxed{\mathrm{E\text{-}Reachability}\text{ is NL-complete}.}
$$
As in ordinary reachability, a zero-length directed <walk> is permitted, so $v=v'$ is an immediate yes-instance. Both the membership procedure and the subdivision <many-one reduction> preserve that case.
Back to article page
