Hi! First of all I give you my compliments for your work. It is very complete and comprehensive. I am struggling to understand the following statement:
I have the feeling that I am missing something. Consider this example: there are three transactions a,b and c, with equal size and fees respectively 2, 1000 and 1. Suppose that a has b as only parent, and b has c as only parent, so in the graph a \to b \to c. Suppose also that inc = \{a\} and pot = \{a,b,c\}. Then adding a to \{b,c\} actually decrease feerate.
BTW the same example seems to go against the following Proposition with best = \{b,c\} and pot as a topologically valid subset of itself.
Can examples like the above appear?
Anyway, this is needed only for the jump ahead optimization, but seems that the heart of the algo is still pretty much effective!