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?

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

0

Reset to default

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.