3
$\begingroup$

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.

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

1 Answer 1

1
+50
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.