Past exam of the computer science course of the University of Oxford / 2015 / Computational complexity / 3 / e

The printed question calls the route a path in a graph and writes $p\subseteq E(G)$, without specifying whether repeated vertices are allowed.^[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 setand directed edgesAfter a directed walk of length $j$ from $(v,0)$, the second coordinate equals $j\mathrm{mod}2$. Therefore there is an even-length directed walk from $v$ to $v^{\prime }$ in $G$ exactly when $(v^{\prime },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}$:Retain $v,v^{\prime }$ 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$. HenceA 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, provingAs in ordinary reachability, a zero-length directed walk is permitted, so $v=v^{\prime }$ is an immediate yes-instance. Both the membership procedure and the subdivision many-one reduction preserve that case.