Thank you!
Ok, here is my understanding so far. This paper, and two other papers it cites, introduce the concept of the “maximum-ratio closure problem”, which is what we’ve been calling “maximum-feerate topologically-valid subset finding”.
1. Maximum-weight closure
To explain it, we first need a simpler problem, the “maximum-weight closure problem”, which, if applied to our setting, is effectively this:
- Input: a transaction graph with dependencies, fees, sizes, where fees can be positive or negative.
- Output: the maximum-fee topologically-valid subset (not feerate), which may be empty. This is trivial if all fees are positive (the entire graph is always maximal then), but nontrivial when negative fees are present.
- Algorithm:
- Assign capacity \infty to each dependency between transactions.
- Add two special nodes to the graph (in addition to the transactions), s (source) and t (sink).
- Add an edge from s to each transaction, with capacity equal to the transaction’s fee.
- Add an adge from each transaction, with capacity 0.
- Run a minimum cut algorithm between s and t. The side of the cut that includes s consists of the highest-fee topologically-valid subset.
2. Closure with ratio above a given \lambda
Given this, one can define a slightly more complex problem:
- Input: a transaction graph with dependencies, fees, sizes, and a feerate \lambda.
- Output: a non-empty topologically-valid subset with feerate \geq \lambda if one exists, or \varnothing otherwise.
- Algorithm:
- Subtract \lambda from the feerates of all transactions, leaving their sizes unchanged (i.e., transform (\operatorname{fee},\operatorname{size}) \rightarrow (\operatorname{fee} - \lambda \operatorname{size}, \operatorname{size})).
- Run the maximum-weight closure algorithm above, and return its result. The empty set has fee 0, so if any topologically-valid subset with higher fee exists, one will be returned, and since \lambda was subtracted from all feerates, the result necessarily has higher feerate than \lambda in this case.
3. Maximum-ratio closure
Finally, we can define the maximum-ratio closure problem, which is asking what the highest \lambda is for which the previous problem has a non-empty set as answer (and what that set is). Three different papers use three different approaches:
- Bisection search:
- Paper: E. L. Lawler, “Sequencing jobs to minimize total weighted completion time subject to precedence constraints”, 1978
- Approach: use a lower and upper bound on the maximum \lambda, and use bisection search to find the highest for which a set exists.
- Complexity: \mathcal{O}(knm \log(n^2/m)), where k is the number of bits in the sizes/fees involved.
- FP algorithm:
- Paper: J.C. Picard and M. Queyranne, “Selected applications of minimum cuts in networks”, 1982.
- Approach: maintain a single best solution, with associated feerate \lambda. Run the previous algorithm with that \lambda as input, and if it returns a non-empty solution, update lambda to be that set’s feerate, and start over.
- Complexity: \mathcal{O}(n^2 m \log(n^2/m)), due to the fact that apparently no more than \mathcal{O}(n) iterations are necessary.
- Parametric min-cut:
- Paper: Giorgio Gallo, Michael D. Grigoriadis, and Robert E. Tarjan, “A Fast Parametric Maximum Flow Algorithm And Applications”, 1989.
- Approach: make the graph itself parametrized by \lambda, and then solve the whole thing generically to find the maximum \lambda, rather than needing multiple improvement steps. I don’t quite get this yet.
- Complexity: \mathcal{O}(nm \log(n^2/m)).
Depending on whether the number of dependencies is linear or quadratic in the number of transactions, this last approach is \mathcal{O}(n^2 \log{n}) or \mathcal{O}(n^3) in the number of transactions. That is however just for a single topologically-valid subset, and for a full linearization we need to potentially run it n times, meaning an overall \mathcal{O}(n^3 \log{n}) or \mathcal{O}(n^4). If it were somehow possible to reuse information from one subset-finding to the next this may be avoided, but that’s not yet clear to me. Also, state of the art on minimum-cut algorithms has improved since 1989, so it’s possible that even better is possible now.