Algorithm to check if vertex belong to infinite path in Graph theory

Question

My purpose is to understand if in a graph $G = \langle V, E\rangle$ given 4 vertices in input (a, b ,c and d) they belong to an infinite path. With infinite path I mean a vertex succession that has a known head without ending.

In other words what I'm trying to do is to find and algorithm that could identify this kind of sequence:

$$ p = a , x_1 , x_2 , x_3, ... , c , ... , d , ... , b , x_i , ... $$

Before ask a question I've thought about using BFS because I have a sort of sequence to find, but I'm stuck at infinite path. I don't know how detect it.

Answer 1

If there is an infinite path then there is also a finite path using two of $a,b,c,d$ as endpoints. However the converse is not true, so the question makes sense. There is some ambiguity about how explicitly one knows the graph.

I will give a graph $H$ which is a disjoint union of paths and has an infinite path exactly if the Collatz $3n+1$ conjecture is false due to an unbounded trajectory. I will then make it into a tree $G$ (plus isolated vertices perhaps) by adding 4 more vertices $a,b,c,d$ which are in an infinite path exactly if $H$ has such a path. I am sure this is much more complicated than it needs to be, but it does work.

Define the function $f$ on positive integers by $f(n)=\frac{n}{2}$ for $n$ even and $f(n)=3n+1$ for $n$ odd. The conjecture is that iteration always arrives at $1.$ Equivalently, for all $n \gt 1$ there is in the list $n,f(n),f(f(n))=f^2(x),f^3(x), \cdots$ a number less than $n.$ If there is a counter-example $n,$ then it is odd and either the sequence above enters a cycle not including $1$ or is the start of a trajectory which increases without bound. It is this second case that would lead to an infinite path .

The vertices of the graph $H$ will be all integer points $(x,y)$ with $2 \leq x \leq y.$ The vast majority will turn out to be isolated points (for example those with $x$ even) so one might also consider generating paths as about to be defined and adding vertices as they arise.

From each point $(x,x),$ start a path $(x,x)=(x,f^0(x)),(x,f(x)),(x,f^2(x)),\cdots\ $ However stop at $(x,y)=(x,f^k(x))$ if it turns out that $f(y)=f^{k+1}(x) \lt x.$

Then this graph $H$ has an infinite path exactly if the conjecture is false. To get $G,$ add four vertices $a,b,c,d$ with edges $(a,b),(b,c),(c,d)$ and also add an edge from $d$ to each $(x,x).$ Then there is an infinite path in $G$ using $a,b,c,d$ exactly if $H$ has an infinite path.

In $G$ every vertex has degree $0,1$ or $2$ except that $d$ has infinite degree. There might be an easy variation which has all vertices of bounded (or at least finite) degree, however I could imagine that there isn't one.

Answer 2

If the graph $G$ can be specified by an algorithm, then the problem of deciding whether it has an infinite path is as hard as the halting problem (that is, algorithmically undecidable).

Let $U$ be a universal Turing machine, let $V$ be the set of all configurations of $U$ (by a configuration we mean a state of $U$, a finite sequence of symbols, and the position of the head), and let $E$ be the set of pairs $(C_1,C_2)$ of configurations such that $U$ gets from $C_1$ to $C_2$ in one step.

This graph $G(U)=(V,E)$ is a collection of paths, which may be finite or infinite. By selecting a vertex $v$ of $G(U)$, we may select a starting configuration $U(T,\emptyset)$, for some other Turing machine $T$ (by a starting configuration we mean the configuration when the tape contains the source code of $T$ and an empty input for $T$). The path containing $v$ is infinite if and only if $T$ does not halt on the empty tape. But the problem whether a given $T$ halts is undecidable.