# zero-sum path problem on a digraph

Consider a digraph $G=(V,A)$ with each arc weighted by either $+1$ or $-1$. A path is called a zero-sum path, if and only if all the arcs in its first half have weight $+1$, and all the arcs in the second half have weight $-1$.

Example: The path $p= +1,+1,+1,-1,-1,-1$ is a zero sum path. However, neither the path $p=+1,-1,+1,+1,-1,-1$ nor the path $p=-1,+1,+1,+1,-1,-1$ is a zero-sum path.

The problem is to preprocess the graph, such that one can answer the following query in constant time: "Is there a zero-sum path between two given nodes $u$ and $v$?"

Given a digraph with $n$ nodes and $m$ edges, the problem could be solved by a Floyd-Warshall-style algorithm in $O(mn)$ time. My question is, whether there exists any better algorithm for solving this problem? Are there any references related to this problem?

• What is "this problem"? ​ ​ – user6973 Feb 11 '17 at 2:59
• Can you elaborate how you can solve it with modification of Floyd algorithm in O (nm)? (Specially if by path you mean simple paths, one can visit every vertex at most once). – Saeed Feb 11 '17 at 17:14
• Is the path allowed to reuse a vertex? Is it allowed to reuse an edge? – Mikhail Rudoy Feb 11 '17 at 20:33
• Yes, you can reuse both nodes and edges. – wei wang Feb 11 '17 at 22:31
• What you use as path is actually like a walk. Your definition of path is far from every book that I know. So you should provide your definition of path in the question not comments. Also it seems you are trolling e.g. multiple time I said you should provide your O (mn) algorithm and you did not address it in your comments. So I prefer to leave this discussion. – Saeed Feb 15 '17 at 8:29