We know from theory that finding a single max likelihood flow is a mcf problem and thus polynomial.
Thus the argument in a completly static network (where noone but us makes a payment) would probably go like this: if you fail at some edge you learn some balance value and there is a finite and polynomial number of rounds / mcf problems that need to be solved to decide if a flow with a capacity of the payment amount exists in the concrete instanciation of the balance graph. You certainly learn at least 1 Satoshi balance in one channel (probably much more) so the algorithm would terminate after at most mC rounds. With m=|E|
We know from theory that finding a single max likelihood flow is a mcf problem and thus polynomial.
Thus the argument in a completly static network (where noone but us makes a payment) would probably go like this: if you fail at some edge you learn some balance value and there is a finite and polynomial number of rounds / mcf problems that need to be solved to decide if a flow with a capacity of the payment amount exists in the concrete instanciation of the balance graph. You certainly learn at least 1 Satoshi balance in one channel (probably much more) so the algorithm would terminate after at most
mCrounds. Withm=|E|