2
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ What is "this problem"? ​ ​ $\endgroup$ – user6973 Feb 11 '17 at 2:59
  • $\begingroup$ 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). $\endgroup$ – Saeed Feb 11 '17 at 17:14
  • $\begingroup$ Is the path allowed to reuse a vertex? Is it allowed to reuse an edge? $\endgroup$ – Mikhail Rudoy Feb 11 '17 at 20:33
  • $\begingroup$ Yes, you can reuse both nodes and edges. $\endgroup$ – wei wang Feb 11 '17 at 22:31
  • 1
    $\begingroup$ 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. $\endgroup$ – Saeed Feb 15 '17 at 8:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.