= Even-length directed reachability
Decide whether a finite <directed graph> has an even-length directed <walk> from a specified source $s$ to a specified target $t$. <Vertices> may repeat and a zero-length <walk> is allowed. The <NL>-completeness proof uses the <graph> of pairs $(v,b)$ with $b\in\{0,1\}$ tracking <integer parity>: every original <edge> flips $b$, and acceptance means reaching $(t,0)$ from $(s,0)$. At most $2|V|-1$ steps are needed in the parity <graph>. For hardness, subdivide every <edge> of an ordinary reachability instance into two directed <edges>. Both constructions are computable by <logspace transducers>. Requiring a simple <path in a graph> in the original <graph> changes the question; deleting an odd closed portion need not preserve <integer parity>.
Back to article page
