<p>The problem (let me call it <strong><span class="math-container">$s$</span>-<span class="math-container">$t$</span>-prime-connectivity</strong>) is in P; more precisely, it is <strong>NL-complete</strong>.</p>
<p>NL-hardness is clear: we can reduce plain <span class="math-container">$s$</span>-<span class="math-container">$t$</span>-connectivity to <span class="math-container">$s$</span>-<span class="math-container">$t$</span>-prime-connectivity just by making sure that every vertex has a self-loop. Then, if there is any path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span>, there are paths of arbitrary lengths <span class="math-container">$\ge n$</span>, and in particular, of prime lengths.</p>
<p>In order to check <span class="math-container">$s$</span>-<span class="math-container">$t$</span>-prime-connectivity in NL, we may use the following characterization, based on an idea of Yonatan N from the comments above:</p>
<blockquote>
<p><strong>Theorem.</strong> For any directed graph <span class="math-container">$G=(V,E)$</span> of size <span class="math-container">$n=|V|$</span>, and <span class="math-container">$s,t\in V$</span>, the following are equivalent:</p>
<ol>
<li><p>There is a path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> of prime length <span class="math-container">$p&gt;n$</span>.</p>
</li>
<li><p>There are a simple cycle <span class="math-container">$C$</span> of length <span class="math-container">$d\le n$</span>, and a path <span class="math-container">$P$</span> from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> of length <span class="math-container">$a$</span> coprime to <span class="math-container">$d$</span> that intersects <span class="math-container">$C$</span>.</p>
</li>
<li><p>There are <span class="math-container">$C$</span> and <span class="math-container">$P$</span> as in 2, where <span class="math-container">$a\le2dn\le2n^2$</span>.</p>
</li>
<li><p>There is a path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> of prime length <span class="math-container">$p&gt;n$</span>, <span class="math-container">$p=n^{O(1)}$</span>.</p>
</li>
</ol>
</blockquote>
<p><strong>Proof:</strong></p>
<p><span class="math-container">$1\to2$</span>: Let <span class="math-container">$P$</span> be a prime-length path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span>. If it has length <span class="math-container">$p&gt;n$</span>, it includes a simple cycle <span class="math-container">$C$</span>; clearly, the length of <span class="math-container">$C$</span>, being <span class="math-container">$\le n$</span>, is coprime to <span class="math-container">$p$</span>.</p>
<p><span class="math-container">$2\to3$</span>: Let <span class="math-container">$u$</span> be a vertex common to <span class="math-container">$P$</span> and <span class="math-container">$C$</span>. Write <span class="math-container">$P$</span> as the concatenation of paths <span class="math-container">$P_0$</span> from <span class="math-container">$s$</span> to <span class="math-container">$u$</span>, and <span class="math-container">$P_1$</span> from <span class="math-container">$u$</span> to <span class="math-container">$t$</span>. It suffices to show that there is a path <span class="math-container">$P'_0$</span> from <span class="math-container">$s$</span> to <span class="math-container">$u$</span> whose length is at most <span class="math-container">$dn$</span>, and congruent to the length of <span class="math-container">$P_0$</span> modulo <span class="math-container">$d$</span>; and similarly for <span class="math-container">$P_1$</span>.</p>
<p>This can be shown by the pigeonhole principle: if the length of <span class="math-container">$P_0$</span> is <span class="math-container">$\le dn$</span>, we are done. Otherwise there are two occurrences of the same vertex in <span class="math-container">$P_0$</span> whose positions in <span class="math-container">$P_0$</span> modulo <span class="math-container">$d$</span> are the same; in other words, <span class="math-container">$P_0$</span> includes a cycle whose length is a multiple of <span class="math-container">$d$</span>. We may delete this subcycle from <span class="math-container">$P_0$</span>. We repeat this process until the length of the path drops below <span class="math-container">$dn$</span>.</p>
<p><span class="math-container">$3\to4$</span>: We may assume <span class="math-container">$a&gt;n$</span>. By <a href="https://en.wikipedia.org/wiki/Linnik%27s_theorem" rel="noreferrer">Linnik’s theorem</a>, the arithmetic progression <span class="math-container">$a,a+d,a+2d,\dots$</span> contains a prime <span class="math-container">$p$</span> of magnitude polynomial in <span class="math-container">$n$</span>; <span class="math-container">$p$</span> is the length of a path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> consisting of <span class="math-container">$P$</span> and several repetitions of <span class="math-container">$C$</span>.</p>
<p><span class="math-container">$4\to1$</span> is trivial.</p>
<p>QED</p>
<p>Condition 4 gives directly an NL-algorithm for <span class="math-container">$s$</span>-<span class="math-container">$t$</span>-prime-connectivity: nondeterministically guess a prime <span class="math-container">$p\le n^c$</span> (where <span class="math-container">$c$</span> is the implied constant), and a path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> of length <span class="math-container">$p$</span>.</p>
<p>In fact, already condition 2 gives an NL-algorithm: nondeterministically choose to either guess a prime <span class="math-container">$p\le n$</span> and a path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> of length <span class="math-container">$p$</span>, or: <span class="math-container">$d\le n$</span>, a vertex <span class="math-container">$u$</span>, a cycle of length <span class="math-container">$d$</span> starting from <span class="math-container">$u$</span>, and a path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> passing through <span class="math-container">$u$</span>, of length coprime to <span class="math-container">$d$</span>. The space required by the algorithm consists of a constant number of vertices, the number <span class="math-container">$d$</span>, and the length of the path being guessed modulo <span class="math-container">$d$</span>; these all fit in <span class="math-container">$O(\log n)$</span> bits.</p>

CC BY-SA 4.0
2018-08-01T15:08:18.333Z
2018-08-01T15:08:18.333Z
2020-06-17T09:38:08.363Z
Emil Jeřábek
<p>I came across the following decision problem, for which I wondered whether anybody of you came across a similar problem and can give me some insight on its nature/complexity.</p>

<p>Given as input a directed labeled graph $G = (V, E)$ and nodes $s,t \in V$, the question is whether there exists a path $\pi$ between $s$ and $t$ whose length equals some prime $p$ (in $\pi$, we allow repetition of vertices so that a self-loop answers this question trivially with yes.)</p>

<p>Thanks!</p>

CC BY-SA 4.0
2018-07-27T02:44:09.977Z
An easy solution is to check whether $(A^p)_{s, t} > 0$, where $A$ denotes the adjacency matrix of $G$. $p$ being prime is irrelevant for this approach, and it seems unlikely to make a difference in general.
Huck Bennett
CC BY-SA 4.0
2018-07-27T11:39:20.873Z
If $p$ is given as part of the input (in unary), the problem is NL-complete. If $p$ is constant, it is in NLogTime.
Emil Jeřábek
CC BY-SA 4.0
2018-07-27T11:55:27.673Z
I think I was a bit unclear in the specification. I consider $p$ not as part of the input, but to be an arbitrary prime number. Thus, the problem is to determine whether there is any directed path between $s$ and $t$ whose length equals $p$ for _some_ prime $p$.
gerald
CC BY-SA 4.0
2018-07-27T20:55:03.020Z
My guess is that this is in $P$. Someone else can probably flesh this out more (or I can get back to this over the weekend), but I believe that much of the problem can be reduced to checking if (1) there exists *any* reachable cycle $C$ along the way and (2) there exists *any* $s-t$ path of length coprime to the $|C|$. If these conditions are both met, we can probably appeal to Dirichlet's theorem on primes in arithmetic progressions. The first is solvable using BFS, and the second can be solved for primes up to $2|V|$ e.g. using @HuckBennett's method, which I believe is going to be sufficient
Yonatan N
CC BY-SA 4.0
2018-07-29T06:23:46.583Z
I think that using Yonatan N's idea and Linnik's theorem, it should hold that if there is a path of prime length, the shortest such path has length at most $n^c$ for some constant $c$. Thus, one can simply try all primes $p\le n^c$, and check if there is a path of length $p$. This puts the problem in NL.
Emil Jeřábek
CC BY-SA 4.0
2018-08-01T00:03:20.660Z
@EmilJeřábek Actually, is it obvious that this works? Consider a graph with a directed "backbone" connecting $s$ to $t$ via a path of length $6$. Off of one vertex in this backbone, we attach a cycle of length $2$. Off of another vertex, we attach a cycle of length $3$. Both of these numbers are not co-prime to $6$ (and thus repeating any one cycle can't help), but the walk that takes both cycles once has length $11$.  Obviously, $11$ is less than the upper bound suggested by Linnik, but does this suggest a flaw in the reasoning? One can look for coprime cycle lengths; does this suffice?
Yonatan N
CC BY-SA 4.0
2018-08-01T07:06:41.573Z
@Yonatan N Well, I didn’t mean it that literally. What I had in mind was that there would be a path of length $a\le n$, and attached to it cycles of lengths $b_1,\dots,b_k\le n$ such that $\gcd(a,b_1,\dots,b_k)=1$. Let $d=\gcd(b_1,\dots,b_k)$. By upper bounds on the Frobenius coin problem, any multiple of $d$ larger than $n^2$ can be written as $\sum_im_ib_i$ with $m_i\ge0$, hence by Linnik’s theorem, there is a prime $p\le n^{O(1)}$  of the form $a+\sum_im_ib_i$. However, I am still unsure if something like the decomposition in the first step really works.
Emil Jeřábek
CC BY-SA 4.0
2018-08-01T14:22:21.083Z
Actually, I think the bounds are easier to prove using the setup in your original comment: just one simple cycle attached to a (not necessarily simple) path. I will make it a proper answer.
Emil Jeřábek
<graph-theory><complexity>
Paths of length $p$ in a Graph, $p$ a prime
gerald
# Paths of length $p$ in a Graph, $p$ a prime

(Asked by: username_0 on 2018-07-26)

I came across the following decision problem, for which I wondered whether anybody of you came across a similar problem and can give me some insight on its nature/complexity.

Given as input a directed labeled graph $G = (V, E)$ and nodes $s,t \in V$, the question is whether there exists a path $\pi$ between $s$ and $t$ whose length equals some prime $p$ (in $\pi$, we allow repetition of vertices so that a self-loop answers this question trivially with yes.)

Thanks!

**Tags:** graph-theory, complexity
> **Comments:**
> **username_1**: An easy solution is to check whether $(A^p)_{s, t} > 0$, where $A$ denotes the adjacency matrix of $G$. $p$ being prime is irrelevant for this approach, and it seems unlikely to make a difference in general.  
> **username_2**: If $p$ is given as part of the input (in unary), the problem is NL-complete. If $p$ is constant, it is in NLogTime.  
> **username_0**: I think I was a bit unclear in the specification. I consider $p$ not as part of the input, but to be an arbitrary prime number. Thus, the problem is to determine whether there is any directed path between $s$ and $t$ whose length equals $p$ for _some_ prime $p$.  
> **username_3**: My guess is that this is in $P$. Someone else can probably flesh this out more (or I can get back to this over the weekend), but I believe that much of the problem can be reduced to checking if (1) there exists *any* reachable cycle $C$ along the way and (2) there exists *any* $s-t$ path of length coprime to the $|C|$. If these conditions are both met, we can probably appeal to Dirichlet's theorem on primes in arithmetic progressions. The first is solvable using BFS, and the second can be solved for primes up to $2|V|$ e.g. using @HuckBennett's method, which I believe is going to be sufficient  
> **username_2**: I think that using Yonatan N's idea and Linnik's theorem, it should hold that if there is a path of prime length, the shortest such path has length at most $n^c$ for some constant $c$. Thus, one can simply try all primes $p\le n^c$, and check if there is a path of length $p$. This puts the problem in NL.  
> **username_3**: @EmilJeřábek Actually, is it obvious that this works? Consider a graph with a directed "backbone" connecting $s$ to $t$ via a path of length $6$. Off of one vertex in this backbone, we attach a cycle of length $2$. Off of another vertex, we attach a cycle of length $3$. Both of these numbers are not co-prime to $6$ (and thus repeating any one cycle can't help), but the walk that takes both cycles once has length $11$.  Obviously, $11$ is less than the upper bound suggested by Linnik, but does this suggest a flaw in the reasoning? One can look for coprime cycle lengths; does this suffice?  
> **username_2**: @Yonatan N Well, I didn’t mean it that literally. What I had in mind was that there would be a path of length $a\le n$, and attached to it cycles of lengths $b_1,\dots,b_k\le n$ such that $\gcd(a,b_1,\dots,b_k)=1$. Let $d=\gcd(b_1,\dots,b_k)$. By upper bounds on the Frobenius coin problem, any multiple of $d$ larger than $n^2$ can be written as $\sum_im_ib_i$ with $m_i\ge0$, hence by Linnik’s theorem, there is a prime $p\le n^{O(1)}$  of the form $a+\sum_im_ib_i$. However, I am still unsure if something like the decomposition in the first step really works.  
> **username_2**: Actually, I think the bounds are easier to prove using the setup in your original comment: just one simple cycle attached to a (not necessarily simple) path. I will make it a proper answer.  

---

## 1 answers

### Answer by username_2 on 2018-08-01. Score: 5

The problem (let me call it **$s$-$t$-prime-connectivity**) is in P; more precisely, it is **NL-complete**.

NL-hardness is clear: we can reduce plain $s$-$t$-connectivity to $s$-$t$-prime-connectivity just by making sure that every vertex has a self-loop. Then, if there is any path from $s$ to $t$, there are paths of arbitrary lengths $\ge n$, and in particular, of prime lengths.

In order to check $s$-$t$-prime-connectivity in NL, we may use the following characterization, based on an idea of Yonatan N from the comments above:

> **Theorem.** For any directed graph $G=(V,E)$ of size $n=|V|$, and $s,t\in V$, the following are equivalent:
>
> 1. There is a path from $s$ to $t$ of prime length $p>n$.
> 2. There are a simple cycle $C$ of length $d\le n$, and a path $P$ from $s$ to $t$ of length $a$ coprime to $d$ that intersects $C$.
> 3. There are $C$ and $P$ as in 2, where $a\le2dn\le2n^2$.
> 4. There is a path from $s$ to $t$ of prime length $p>n$, $p=n^{O(1)}$.

**Proof:**

$1\to2$: Let $P$ be a prime-length path from $s$ to $t$. If it has length $p>n$, it includes a simple cycle $C$; clearly, the length of $C$, being $\le n$, is coprime to $p$.

$2\to3$: Let $u$ be a vertex common to $P$ and $C$. Write $P$ as the concatenation of paths $P\_0$ from $s$ to $u$, and $P\_1$ from $u$ to $t$. It suffices to show that there is a path $P'\_0$ from $s$ to $u$ whose length is at most $dn$, and congruent to the length of $P\_0$ modulo $d$; and similarly for $P\_1$.

This can be shown by the pigeonhole principle: if the length of $P\_0$ is $\le dn$, we are done. Otherwise there are two occurrences of the same vertex in $P\_0$ whose positions in $P\_0$ modulo $d$ are the same; in other words, $P\_0$ includes a cycle whose length is a multiple of $d$. We may delete this subcycle from $P\_0$. We repeat this process until the length of the path drops below $dn$.

$3\to4$: We may assume $a>n$. By [Linnik’s theorem](https://en.wikipedia.org/wiki/Linnik%27s_theorem), the arithmetic progression $a,a+d,a+2d,\dots$ contains a prime $p$ of magnitude polynomial in $n$; $p$ is the length of a path from $s$ to $t$ consisting of $P$ and several repetitions of $C$.

$4\to1$ is trivial.

QED

Condition 4 gives directly an NL-algorithm for $s$-$t$-prime-connectivity: nondeterministically guess a prime $p\le n^c$ (where $c$ is the implied constant), and a path from $s$ to $t$ of length $p$.

In fact, already condition 2 gives an NL-algorithm: nondeterministically choose to either guess a prime $p\le n$ and a path from $s$ to $t$ of length $p$, or: $d\le n$, a vertex $u$, a cycle of length $d$ starting from $u$, and a path from $s$ to $t$ passing through $u$, of length coprime to $d$. The space required by the algorithm consists of a constant number of vertices, the number $d$, and the length of the path being guessed modulo $d$; these all fit in $O(\log n)$ bits.


---

