How can algorithms with nested combinatorial searches be quasi-linear?
As I see it, that is a combinatorial problem, i.e. exhausting which number and composition of vertices constitutes a suitable set.


No, it's just a selection problem, for which there are well-known linear algorithms.