renepickhardt
Proof correctness and runtime of the roundbased algorithm. Especially payment delivery is not np hard
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|
Not sure if concurrent payments and topology changes from edge adding removal are introduced the decision problem if a flow of capacity = payment amount on the balance graph exists can be solved / decided at all