That, I think is not accurate to say. For a fixed \lambda finding a subset that maximizes \mathrm{fee}_x - \lambda \mathrm{size}_x simply transforms to the “maximum weight closure problem” that can be solved with any min-cut finding algorithm. The “max. weight closure problem” is a subproblem of your original “maximum feerate closure problem”. The novelty of GGT is that you don’t need to do bisection to solve the “maximum feerate closure” and the computation complexity of the feerate problem stays the same as the computational complexity of a single “max. weight closure”.
2 Likes