# Deciding whether there are directed paths between two vertices of all possible lengths

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.

## 1 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.

• 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$. Commented Jun 12 at 0:45