4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Please don't edit a question by adding "EDIT: some extra stuff". Instead, edit the question to be what it should have been from the start, i.e., to be self-contained for someone who encounters it from the beginning. There is no need to preserve the prior version of the question: we have a revision history for that. $\endgroup$ – D.W. Sep 29 '14 at 16:37
  • $\begingroup$ How is this now different from the pior question? FrankW's answer there states that it's NP-complete, which answers your question. If it's not "trivial" as he states, ask for clarification in a comment. $\endgroup$ – Raphael Sep 29 '14 at 17:54
  • $\begingroup$ Its a different problem, before we only allowed a path between vertices, but now we allow a walk containing repeated vertices. $\endgroup$ – Tyler Durden Sep 29 '14 at 18:48
  • $\begingroup$ @Raphael, I added a paragraph at the end to explain why it is not trivial (in particular, it is not obvious that this question is in NP, because we are talking about walks, rather than paths). Based on your comment, I tried editing it a little more just now to explain even further. Does that help? $\endgroup$ – D.W. Sep 30 '14 at 20:18
4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The languages $L_k$ with more than one type of paren are captured by multiple context-free grammars. I'm quite sure the corresponding language class is closed under intersection with regular languages, but I don't remember, if emptiness is decidable for them. (And I don't have much access to literature right now.) $\endgroup$ – FrankW Oct 1 '14 at 16:07
  • $\begingroup$ Sorry, but I fail to see the $\mathbb Q$ problem. Why not multiply everything with the LCM of the denominators and stay within $\mathbb Z$ that way? $\endgroup$ – Hendrik Jan Oct 1 '14 at 17:04
  • $\begingroup$ The problem is about $\mathbb{R}$ rather than $\mathbb{Q}$, or if you prefer, about $\mathbb{Z}^d$. I already take into account clearing of denominators. $\endgroup$ – Yuval Filmus Oct 1 '14 at 17:49

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.