# Given a directed graph with edge weights $0$ or $1$, is there a way to find an odd cycle in $\mathsf{NC}$?

Given a directed graph with edge weights $$0$$ or $$1$$, is there a way to find an odd weight cycle in $$\mathsf{NC}$$? I think the decision version is in $$\mathsf{NC}$$, but I am not sure about the search version.

$$\mathsf{NC}$$ is a class of decision problems. I assume you mean to ask whether the search version is in $$\mathsf{FNC}$$, where for any class $$C$$ of decision problems, $$\mathsf FC$$ is the class of functions $$F\colon\{0,1\}^*\to\{0,1\}^*$$ such that $$|F(x)|\le|x|^{O(1)}$$, and the bitgraph $$\{(x,1^i):\text{ith bit of F(x) is 1}\}$$ is decidable in $$C$$.

The answer is positive; better yet, such a cycle—if it exists—can be found in $$\mathsf{FNL}$$.

First, a simpler problem:

Lemma: Given a directed graph $$G$$ and two vertices $$s$$ and $$t$$ such that $$t$$ is reachable from $$s$$, we can find a directed path from $$s$$ to $$t$$ by an $$\mathsf{FNL}$$ function.

Proof: We will define a canonical path from $$s$$ to $$t$$ such that given $$i$$ in unary, we can find the $$i$$th bit of the description of the path in $$\mathsf{NL}$$.

Recall that the problem “given $$l$$ and vertices $$s$$ and $$t$$, is $$t$$ reachable from $$s$$ in $$l$$ steps?” is in $$\mathsf{NL}$$, and so is its complement by the Immerman—Szelepcsényi theorem. Thus, we can find the least length $$l$$ of a path from $$s$$ to $$t$$ by a nondeterministic logspace algorithm: we nondeterministically guess and verify the correct answer to the above-mentioned problem for $$l=0,1,2,\dots$$ until the answer is positive.

Then we define a path $$x_0,\dots,x_l$$ by $$x_0=s$$, and for each $$j, $$x_{j+1}$$ is the least vertex (in numerical order, identifying the set of vertices with $$[n]$$) such that there is an edge from $$x_j$$ to $$x_{j+1}$$, and $$t$$ is reachable from $$x_{j+1}$$ in $$l-j-1$$ steps. As above, given $$x_j$$, we can compute $$x_{j+1}$$ in nodeterministic logspace. Thus, we can compute vertices of the path one by one (we do not store the whole path, but only the current $$x_j$$). We keep track of the bit-length of the description of the path, and upon reaching the $$i$$th bit, we output it. QED

Now, for the problem in the question, we proceed similarly. Let $$G=(V,E)$$ be the input graph, and for $$j=1,2$$, let $$G_j=(V,E_j)$$ be the graph with an edge from $$u$$ to $$v$$ iff there exists a path from $$u$$ to $$v$$ in $$G$$ that uses exactly $$j$$ edges of weight $$1$$. The original problem is equivalent to: find vertices $$u$$ and $$v$$, a path from $$u$$ to $$v$$ in $$G$$ that lifts a path in $$G_2$$, and a path from $$v$$ to $$u$$ in $$G$$ that lifts an edge in $$G_1$$.

Note that $$E_1$$ and $$E_2$$ are both $$\mathsf{NL}$$-computable. Using a similar strategy as above, we compute the least $$u$$ and $$v$$ in numerical order for which such paths exist, and the least length $$l$$ of a $$G_2$$-path from $$u$$ to $$v$$. Define a $$G_2$$-path $$x_0,\dots,x_l$$ from $$u$$ to $$v$$ such that $$x_0=u$$ and $$x_{j+1}$$ is the least vertex with a $$G_2$$-edge from $$x_j$$ from which $$v$$ is $$G_2$$-reachable in $$l-j-1$$ steps. For each $$j, we similarly define a canonical $$G$$-path from $$x_j$$ to $$x_{j+1}$$ that goes through two edges of weight $$1$$, and a $$G$$-path from $$v$$ to $$u$$ that goes through one edge of weight $$1$$. The resulting path is computable vertex by vertex in nondeterministic logspace, keeping track of the last constructed $$x_j$$, the last constructed vertex of the $$G$$-path from $$x_j$$ to $$x_{j+1}$$, and the bit-length of the description of the path so far.