Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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!
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:
There is a path from $s$ to $t$ of prime length $p>n$.
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$.
There are $C$ and $P$ as in 2, where $a\le2dn\le2n^2$.
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, 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.
