<p>While the initial problem of determining if an integer LRS has a zero is indeed not known to be decidable, the graph problem you mention is very much decidable.
It is simply used for coNP-hardness in the paper, but is in fact coNP-complete:</p>
<p>If we see the graph as a non-deterministic automaton with a single letter, with <span class="math-container">$v_1$</span> its initial state and <span class="math-container">$v_2$</span> its final state, the question becomes whether this automaton is universal or not.
As it has an equivalent DFA of exponential size, if there is a word <span class="math-container">$a^k$</span> that is not accepted, then there is one of at most exponential size.
The coNP algorithm consists in guessing <span class="math-container">$k$</span> in binary, and then checking that <span class="math-container">$a^k$</span> is not accepted using fast matrix exponentiation.</p>

CC BY-SA 4.0
2024-06-12T00:45:54.003Z
Perhaps an easier and graph theoretic proof of hardness is a reduction from $s$-$t$ Hamiltonian Path (given graph $G$ and $s,t$, is there an $s$-$t$ path that spans all vertices?). One can reduce $s$-$t$-Hamiltonian Path to the OPs problem as follows. Given $G$, $s,t$, construct  dummy paths of lengths $1$ to $n-1$ from $s$ to $t$ and add them to $G$.
Chandra Chekuri
CC BY-SA 4.0
2024-06-11T20:17:54.053Z
2024-06-11T20:17:54.053Z
Corto
<p>I recently read a paper <em>The presence of a zero in an integer linear recurrent sequence is NP-hard to decide</em> by Blondel and Portier, in which they prove the statement</p>
<blockquote>
<p>The problem of determining for a given directed graph <span class="math-container">$G$</span> and vertices <span class="math-container">$V_1$</span> and <span class="math-container">$V_2$</span> of <span class="math-container">$G$</span> if there are directed paths from <span class="math-container">$V_1$</span> to <span class="math-container">$V_2$</span> of all possible lengths <span class="math-container">$k \geq 1$</span> is coNP-hard.</p>
</blockquote>
<p>Beyond complexity, it is not known if this problem is decidable.</p>
<p>My knowledge of graph theory is very weak, although even so this statement was surprising to me: it seems as though such a problem could be easy to decide by inspecting the graph/adjacency matrix in some way.</p>
<p>Can someone explain why my intuition is wrong here, and why this problem is in fact hard and not known to be decidable?  To be clear, I do not have an algorithm solving this, I suppose I can see why this may not be decidable, since it is asking whether some component of an adjacency matrix of a directed graph remains positive under <em>all</em> powers, but even so my intuition is not solid.</p>

<graph-theory><computability>
Deciding whether there are directed paths between two vertices of all possible lengths
user918212
# Deciding whether there are directed paths between two vertices of all possible lengths

(Asked by: username_0 on 2024-06-11)

I recently read a paper *The presence of a zero in an integer linear recurrent sequence is NP-hard to decide* by Blondel and Portier, in which they prove the statement

> The problem of determining for a given directed graph $G$ and vertices $V\_1$ and $V\_2$ of $G$ if there are directed paths from $V\_1$ to $V\_2$ of all possible lengths $k \geq 1$ is coNP-hard.

Beyond complexity, it is not known if this problem is decidable.

My knowledge of graph theory is very weak, although even so this statement was surprising to me: it seems as though such a problem could be easy to decide by inspecting the graph/adjacency matrix in some way.

Can someone explain why my intuition is wrong here, and why this problem is in fact hard and not known to be decidable? To be clear, I do not have an algorithm solving this, I suppose I can see why this may not be decidable, since it is asking whether some component of an adjacency matrix of a directed graph remains positive under *all* powers, but even so my intuition is not solid.

**Tags:** graph-theory, computability


---

## 1 answers

### Answer by username_1 on 2024-06-11. Score: 4 | Accepted answer

While the initial problem of determining if an integer LRS has a zero is indeed not known to be decidable, the graph problem you mention is very much decidable.
It is simply used for coNP-hardness in the paper, but is in fact coNP-complete:

If we see the graph as a non-deterministic automaton with a single letter, with $v\_1$ its initial state and $v\_2$ its final state, the question becomes whether this automaton is universal or not.
As it has an equivalent DFA of exponential size, if there is a word $a^k$ that is not accepted, then there is one of at most exponential size.
The coNP algorithm consists in guessing $k$ in binary, and then checking that $a^k$ is not accepted using fast matrix exponentiation.

> **Comments:**
> **username_2**: Perhaps an easier and graph theoretic proof of hardness is a reduction from $s$-$t$ Hamiltonian Path (given graph $G$ and $s,t$, is there an $s$-$t$ path that spans all vertices?). One can reduce $s$-$t$-Hamiltonian Path to the OPs problem as follows. Given $G$, $s,t$, construct  dummy paths of lengths $1$ to $n-1$ from $s$ to $t$ and add them to $G$.  

---

