I didn't immediately see what guaranteed that the binary search would run in polynomial time. In case anyone else doesn't see it:
There are O(V!) possible paths. Assuming binary search actually halves the search space each iteration, it will run in O(log(V!)) = O(log(n(n-1)...*1)) = O(log(n) + log(n-1) + ... + log(1)), which is clearly polynomial.
There are O(V!) possible paths. Assuming binary search actually halves the search space each iteration, it will run in O(log(V!)) = O(log(n(n-1)...*1)) = O(log(n) + log(n-1) + ... + log(1)), which is clearly polynomial.