Determine efficiently whether A can get infinitely larger than B by following a walk in the given graph

Question

Person $A$ is chasing person $B$. Both people can only travel between $n$ vertices of a graph by running through one of $m$ one-way pipes labelled $1,2,\cdots, m$. For each pipe we know the starting and ending vertex. Each pipe has two values $A_i, B_i$ which are positive real numbers and represent the multipliers of person $A$'s and $B$'s heights as they run through the pipe. For example, if person $A$ and person $B$ currently both have height $2$, if they run through the pipe with $A_i =1, B_i = 2$, then person B will now have height $4$ while person $A$ will have height $2$.

$A$ starts running at a vertex $s$ while $B$ starts at s an instant later and will chase $A$ at the same speed later. You can treat $A$ and $B$ as a single object whose trajectory is entirely determined by $A$.

Given the graph (with no duplicate edges or self-loops) and the starting vertex $s$, how can I determine in $O(nm)$ time or faster if it's possible for $A$ to lead $B$ through a sequence of pipes so that $A$ gets infinitely larger than $B$? Provide a justification for the algorithm.

I was thinking of creating a new graph where there is a negative weight cycle if and only if it's possible for $A$ to be infinitely larger than $B$ after travelling through a sequence of pipes. Then I could use the Bellman Ford algorithm to solve the problem in $O(nm)$ time. But I'm not sure how to find this graph.

Answer 1

You've the right idea. Yuval's comment provides the missing trick. Here is the algorithm that connects the dots.

1. For each pipe $i$ with $A_i$ and $B_i$ from vertex $u$ to vertex $v$, we add an edge of weight $\log(B_i/A_i)$ from $u$ to $v$. Let $G$ be the graph with the given $n$ vertices and $m$ edges just added. It is the graph you were thinking of.
2. Apply Bellman–Ford algorithm with $s$ as the source to detect whether there is a negative-weight cycle in $G$ reachable from $s$.
3. If there is, it is possible for $A$ to lead $B$ through a sequence of pipes starting from $s$ so that $A$ gets infinitely larger than $B$. Otherwise, no.

The idea is that the sum of weights along a walk in $G$ corresponds to the logarithm of the change of ratios of $B$'s height to $A$'s height when $A$ and $B$ have walked that walk. A negative-weight cycle means the ratio of $B$'s height to $A$'s height becomes smaller when $A$ and $B$ have walked that cycle once.

The algorithm runs in $O(mn)$ time.