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

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.

• Hint: use the log operation. Mar 10, 2022 at 22:42
• @YuvalFilmus can you confirm whether there’s an O(nm) time algorithm solving this problem? A yes or no is enough. Mar 12, 2022 at 5:19

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.