Decide whether there exists a walk of weight exactly k

Question

Consider the following problem:

Input: a directed graph $G = (V,E,\omega)$ where $\omega : E \longrightarrow \mathbb{Z}$, two vertices $v_1, v_2 \in V$, and a weight $k \in \mathbb{Z}$

Question: Does there exist a walk from $v_1$ to $v_2$ with weight exactly $k$?

The weight of a walk is simply the sum of all edges in the path. Note that the walk can contain cycles.

Is this problem decidable? Is there any algorithm to solve this problem, if I don't care about the running time? My problem is that since we can have edges weighted with either positive or negative integers, it is hard to determine when to stop or turn back when it gets too low or too high.

For example, given the graph $G$ where $V = \{ v_1,v_2 \}$ and $E = \{e_1:(v_1,v-1), e_2:(v_1,v_2)\}$ and $\omega(e_1)=-2$ and $\omega(e_2)=1$, the question could be is there a walk from $v_1$ to $v_2$ with weight $-99$. The algorithm should say yes, as there is a walk starting from $v_1$ and self looping 50 times over edge $e_1$ before taking edge $e_2$ and terminating.

I previously asked about the complexity of a similar problem here, but there I was focused on the complexity of the problem. Others have shown that this problem is NP-hard. Also, the previously question asked about a path, whereas here I am asking about a walk (a vertex might be visited multiple times); the version with paths is in NP and thus decidable, but here I am asking about walks rather than paths.

Notice that this problem is not trivial, largely because we are talking about walks rather than simple paths. There is no a priori upper bound on the length of a walk from $v_1$ to $v_2$, so just enumerating all possible walks might never terminate. Also, the graph could contain exponentially many cycles, and the walk might visit some of them any number of times. And, there is no obvious upper bound on the number of times that we traverse any given cycle. In particular, it is not obvious whether this problem is in NP or not. A straightforward reduction to integer linear programming (an integer variable for each edge, counting how many times the walk traverses that edge) runs into the difficulty that it is not clear how to ensure that you have a walk and not a flow.

Answer 1

We start by converting your graph into an NFA $A$, by replacing the weights with strings. Positive weights $k > 0$ are replaced by $a^k$, negative weights $k < 0$ are replaced by $b^{-k}$, and zero weights are replaced by $\epsilon$ (the empty string). We make $v_1$ the initial state and $v_2$ the only accepting state. Consider now the context-free language $L_k = \{ w : \#_a(w) - \#_b(w) = k \}$. We construct a context-free grammar for $L_k \cap A$ and check whether $L_k \cap A = \emptyset$.

The size of the generated NFA is polynomial in $n + \sum_{ij} |w_{ij}|$ where $n$ is the number of vertices and $w_{ij}$ are the weights. The size of a grammar for $L_k$ is polynomial in $k$. In order to intersect it with $A$, we convert it to a PDA, use the product construction, and then convert back. We get a CFG of size polynomial in $n + \sum_{ij} |w_{ij}| + k$. Checking emptyness takes polynomial time, so the entire algorithm takes time polynomial in $n + \sum_{ij} |w_{ij}| + k$, showing that the problem is in NP if the weights and the target sum are encoded in unary (otherwise the bound we get is only NEXP).

Interestingly, this argument doesn't work for real weights. The natural extension would be to find a basis for the weights over $\mathbb{Q}$, clear off the denominators, and have a pair of symbols $(a_i,b_i)$ for each element in the basis. The argument fails since $L_{\mathbf{k}} = \{ w : \forall i \#_{a_i}(w) - \#_{b_i}(w) = k_i \}$ is not context-free if there is more than one pair of symbols.

Is the problem with real weights (given as linear combinations over $\mathbb{Q}$ of some $\mathbb{Q}$-linearly independent set) decidable?