<p>Consider a digraph $G=(V,A)$ with each arc weighted by either $+1$ or $-1$. A path is called a <em>zero-sum path</em>, 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$.</p>

<p><strong>Example:</strong> 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.</p>

<p>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$?"</p>

<p>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?</p>

CC BY-SA 3.0
2017-02-11T17:14:52.770Z
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
CC BY-SA 3.0
2017-02-11T20:33:41.447Z
Is the path allowed to reuse a vertex? Is it allowed to reuse an edge?
Mikhail Rudoy
CC BY-SA 3.0
2017-02-11T22:31:52.240Z
Yes, you can reuse both nodes and edges.
wei wang
CC BY-SA 3.0
2017-02-13T09:23:46.063Z
If one is allowed to reuse edges and vertices then it is not a path anymore. Please edit the question and modify all misleading information. Also still the O (mn) algorithm looks like a wrong claim.
Saeed
CC BY-SA 3.0
2017-02-14T00:45:09.747Z
In my original question, I didn't require the paths to be simple paths. Why cannot reuse nodes and edges?
wei wang
CC BY-SA 3.0
2017-02-14T23:07:02.630Z
One may argue that reusing nodes in path is allowed, but at least I never seen a definition of path which allows reuse of edges. If you have any graph theory text book which allows reuse of edges then provide a refernce. BTW this is not the only issue with the problem, the other issue is that you claimed modification of normal all pair shortest paths algorithm works. I have no idea if it is in P or NPC and have no time to think about it, but I also don't see a simple modification of apsp algorithms. If you have it you should present it to show what you did.
Saeed
CC BY-SA 3.0
2017-02-15T00:41:40.617Z
What's your definition of "reuse"? I can have a path p=1,1,1,2,3 where (1,1) is labeled by "+1", (1,2) and (2,3) are labeled by "-1". I assume your definition of reused edge is (1,1). The path p is certainly the one we want to compute.
wei wang
CC BY-SA 3.0
2017-02-15T08:29:58.393Z
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
<graph-theory><graph-algorithms>
zero-sum path problem on a digraph
wei wang
# zero-sum path problem on a digraph

(Asked by: username_0 on 2017-02-11)

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?

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: 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).  
> **username_2**: Is the path allowed to reuse a vertex? Is it allowed to reuse an edge?  
> **username_0**: Yes, you can reuse both nodes and edges.  
> **username_1**: If one is allowed to reuse edges and vertices then it is not a path anymore. Please edit the question and modify all misleading information. Also still the O (mn) algorithm looks like a wrong claim.  
> **username_0**: In my original question, I didn't require the paths to be simple paths. Why cannot reuse nodes and edges?  
> **username_1**: One may argue that reusing nodes in path is allowed, but at least I never seen a definition of path which allows reuse of edges. If you have any graph theory text book which allows reuse of edges then provide a refernce. BTW this is not the only issue with the problem, the other issue is that you claimed modification of normal all pair shortest paths algorithm works. I have no idea if it is in P or NPC and have no time to think about it, but I also don't see a simple modification of apsp algorithms. If you have it you should present it to show what you did.  
> **username_0**: What's your definition of "reuse"? I can have a path p=1,1,1,2,3 where (1,1) is labeled by "+1", (1,2) and (2,3) are labeled by "-1". I assume your definition of reused edge is (1,1). The path p is certainly the one we want to compute.  
> **username_1**: 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.  

---

## 0 answers

