6
$\begingroup$

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!

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ 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. $\endgroup$ – Huck Bennett Jul 27 '18 at 2:44
  • $\begingroup$ If $p$ is given as part of the input (in unary), the problem is NL-complete. If $p$ is constant, it is in NLogTime. $\endgroup$ – Emil Jeřábek Jul 27 '18 at 11:39
  • 1
    $\begingroup$ 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$. $\endgroup$ – gerald Jul 27 '18 at 11:55
  • 2
    $\begingroup$ 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 $\endgroup$ – Yonatan N Jul 27 '18 at 20:55
  • 2
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Jul 29 '18 at 6:23
5
$\begingroup$

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, 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.