<p><span class="math-container">$\mathsf{NC}$</span> is a class of decision problems. I assume you mean to ask whether the search version is in <span class="math-container">$\mathsf{FNC}$</span>, where for any class <span class="math-container">$C$</span> of decision problems, <span class="math-container">$\mathsf FC$</span> is the class of functions <span class="math-container">$F\colon\{0,1\}^*\to\{0,1\}^*$</span> such that <span class="math-container">$|F(x)|\le|x|^{O(1)}$</span>, and the bitgraph
<span class="math-container">$$\{(x,1^i):\text{$i$th bit of $F(x)$ is $1$}\}$$</span>
is decidable in <span class="math-container">$C$</span>.</p>
<p>The answer is positive; better yet, such a cycle—if it exists—can be found in <span class="math-container">$\mathsf{FNL}$</span>.</p>
<p>First, a simpler problem:</p>
<blockquote>
<p><strong>Lemma:</strong> Given a directed graph <span class="math-container">$G$</span> and two vertices <span class="math-container">$s$</span> and <span class="math-container">$t$</span> such that <span class="math-container">$t$</span> is reachable from <span class="math-container">$s$</span>, we can find a directed path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> by an <span class="math-container">$\mathsf{FNL}$</span> function.</p>
</blockquote>
<p><strong>Proof:</strong>
We will define a canonical path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> such that given <span class="math-container">$i$</span> in unary, we can find the <span class="math-container">$i$</span>th bit of the description of the path in <span class="math-container">$\mathsf{NL}$</span>.</p>
<p>Recall that the problem “given <span class="math-container">$l$</span> and vertices <span class="math-container">$s$</span> and <span class="math-container">$t$</span>, is <span class="math-container">$t$</span> reachable from <span class="math-container">$s$</span> in <span class="math-container">$l$</span> steps?” is in <span class="math-container">$\mathsf{NL}$</span>, and so is its complement by the Immerman—Szelepcsényi theorem. Thus, we can find the least length <span class="math-container">$l$</span> of a path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> by a nondeterministic logspace algorithm: we nondeterministically guess and verify the correct answer to the above-mentioned problem for <span class="math-container">$l=0,1,2,\dots$</span> until the answer is positive.</p>
<p>Then we define a path <span class="math-container">$x_0,\dots,x_l$</span> by <span class="math-container">$x_0=s$</span>, and for each <span class="math-container">$j&lt;l$</span>, <span class="math-container">$x_{j+1}$</span> is the least vertex (in numerical order, identifying the set of vertices with <span class="math-container">$[n]$</span>) such that there is an edge from <span class="math-container">$x_j$</span> to <span class="math-container">$x_{j+1}$</span>, and <span class="math-container">$t$</span> is reachable from <span class="math-container">$x_{j+1}$</span> in <span class="math-container">$l-j-1$</span> steps. As above, given <span class="math-container">$x_j$</span>, we can compute <span class="math-container">$x_{j+1}$</span> 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 <span class="math-container">$x_j$</span>). We keep track of the bit-length of the description of the path, and upon reaching the <span class="math-container">$i$</span>th bit, we output it. QED</p>
<p>Now, for the problem in the question, we proceed similarly. Let <span class="math-container">$G=(V,E)$</span> be the input graph, and for <span class="math-container">$j=1,2$</span>, let <span class="math-container">$G_j=(V,E_j)$</span> be the graph with an edge from <span class="math-container">$u$</span> to <span class="math-container">$v$</span> iff there exists a path from <span class="math-container">$u$</span> to <span class="math-container">$v$</span> in <span class="math-container">$G$</span> that uses exactly <span class="math-container">$j$</span> edges of weight <span class="math-container">$1$</span>. The original problem is equivalent to: find vertices <span class="math-container">$u$</span> and <span class="math-container">$v$</span>, a path from <span class="math-container">$u$</span> to <span class="math-container">$v$</span> in <span class="math-container">$G$</span> that lifts a path in <span class="math-container">$G_2$</span>, and a path from <span class="math-container">$v$</span> to <span class="math-container">$u$</span> in <span class="math-container">$G$</span> that lifts an edge in <span class="math-container">$G_1$</span>.</p>
<p>Note that <span class="math-container">$E_1$</span> and <span class="math-container">$E_2$</span> are both <span class="math-container">$\mathsf{NL}$</span>-computable. Using a similar strategy as above, we compute the least <span class="math-container">$u$</span> and <span class="math-container">$v$</span> in numerical order for which such paths exist, and the least length <span class="math-container">$l$</span> of a <span class="math-container">$G_2$</span>-path from <span class="math-container">$u$</span> to <span class="math-container">$v$</span>. Define a <span class="math-container">$G_2$</span>-path <span class="math-container">$x_0,\dots,x_l$</span> from <span class="math-container">$u$</span> to <span class="math-container">$v$</span> such that <span class="math-container">$x_0=u$</span> and <span class="math-container">$x_{j+1}$</span> is the least vertex with a <span class="math-container">$G_2$</span>-edge from <span class="math-container">$x_j$</span> from which <span class="math-container">$v$</span> is <span class="math-container">$G_2$</span>-reachable in <span class="math-container">$l-j-1$</span> steps. For each <span class="math-container">$j&lt;l$</span>, we similarly define a canonical <span class="math-container">$G$</span>-path from <span class="math-container">$x_j$</span> to <span class="math-container">$x_{j+1}$</span> that goes through two edges of weight <span class="math-container">$1$</span>, and a <span class="math-container">$G$</span>-path from <span class="math-container">$v$</span> to <span class="math-container">$u$</span> that goes through one edge of weight <span class="math-container">$1$</span>. The resulting path is computable vertex by vertex in nondeterministic logspace, keeping track of the last constructed <span class="math-container">$x_j$</span>, the last constructed vertex of the <span class="math-container">$G$</span>-path from <span class="math-container">$x_j$</span> to <span class="math-container">$x_{j+1}$</span>, and the bit-length of the description of the path so far.</p>

CC BY-SA 4.0
2024-09-20T20:33:41.697Z
Hi Emil, thanks for you answer! I am not familiar with Immerman—Szelepcsényi and I'm not sure why it is needed here. Why can't we simply check if there is a path for l=n, n-1,n-2.... and keep updating a counter whenever a path exists. The final value of counter will be the length of the shortest path.
Agile_Eagle
CC BY-SA 4.0
2024-09-20T20:35:05.307Z
Also, could you clarify what you mean by 'lifts a path' and 'lifts an edge'?
Agile_Eagle
CC BY-SA 4.0
2024-09-21T11:16:52.053Z
If you nondeterministically try to guess a path of length $n,n-1,n-2,\dots$, and the machine finds a path of length $7$, but no path of shorter length, you do not know whether (1) the shortest path is indeed of length $7$, or whether (2) there is a path of length $4$, but the machine guessed it wrong. In order to compute the minimal length, you need to have a way of nondeterministically certifying *both* existence and nonexistence of paths of given length.
Emil Jeřábek
CC BY-SA 4.0
2024-09-21T11:27:06.693Z
Lifting means the obvious thing. By definition, there is an edge in $G_j$ from $u$ to $v$ iff there exists a path in $G$ from $u$ to $v$ that has exactly $j$ edges of weight $1$ (and arbitrary edges of weight $0$). Any such path is said to lift the $G_j$ edge $u\to v$. Then, a path $p$ in $G$ lifts a path $u_0\dots u_k$ in $G_j$ if $p$ is a concatenation of paths $p_0,\dots,p_{k-1}$ such that $p_i$ lifts the edge $u_i\to u_{i+1}$ for each $i<k$.
Emil Jeřábek
CC BY-SA 4.0
2024-07-28T09:49:51.540Z
2024-07-28T09:49:51.540Z
Emil Jeřábek
<p>Given a directed graph with edge weights <span class="math-container">$0$</span> or <span class="math-container">$1$</span>, is there a way to find an odd weight cycle in <span class="math-container">$\mathsf{NC}$</span>? I think the decision version is in <span class="math-container">$\mathsf{NC}$</span>, but I am not sure about the search version.</p>

<cc.complexity-theory><graph-theory><circuit-complexity><parallel>
Given a directed graph with edge weights $0$ or $1$, is there a way to find an odd cycle in $\mathsf{NC}$?
Agile_Eagle
# Given a directed graph with edge weights $0$ or $1$, is there a way to find an odd cycle in $\mathsf{NC}$?

(Asked by: username_0 on 2024-07-27)

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.

**Tags:** cc.complexity-theory, graph-theory, circuit-complexity, parallel

---

## 1 answers

### Answer by username_1 on 2024-07-28. Score: 6 | Accepted answer

$\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{$i$th 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.

> **Comments:**
> **username_0**: Hi Emil, thanks for you answer! I am not familiar with Immerman—Szelepcsényi and I'm not sure why it is needed here. Why can't we simply check if there is a path for l=n, n-1,n-2.... and keep updating a counter whenever a path exists. The final value of counter will be the length of the shortest path.  
> **username_0**: Also, could you clarify what you mean by 'lifts a path' and 'lifts an edge'?  
> **username_1**: If you nondeterministically try to guess a path of length $n,n-1,n-2,\dots$, and the machine finds a path of length $7$, but no path of shorter length, you do not know whether (1) the shortest path is indeed of length $7$, or whether (2) there is a path of length $4$, but the machine guessed it wrong. In order to compute the minimal length, you need to have a way of nondeterministically certifying *both* existence and nonexistence of paths of given length.  
> **username_1**: Lifting means the obvious thing. By definition, there is an edge in $G_j$ from $u$ to $v$ iff there exists a path in $G$ from $u$ to $v$ that has exactly $j$ edges of weight $1$ (and arbitrary edges of weight $0$). Any such path is said to lift the $G_j$ edge $u\to v$. Then, a path $p$ in $G$ lifts a path $u_0\dots u_k$ in $G_j$ if $p$ is a concatenation of paths $p_0,\dots,p_{k-1}$ such that $p_i$ lifts the edge $u_i\to u_{i+1}$ for each $i<k$.  

---

