Kidney exchange programs match incompatible donor-recipient pairs into cycles and chains: A's donor gives to B, B's donor gives to C, C's donor gives to A. Finding the maximum number of transplants in a pool of pairs is NP-hard, but the relevant parameter isn't the pool size — it's the number of successful transplants, t. Algorithms parameterized by t are practical because t is small even when the pool is large.
Jia, Saurabh, and Zehavi (arXiv:2603.18471) cut the base of the exponential from 14.34 to 6.855 using representative sets — a technique from algebraic algorithms that compresses combinatorial search spaces by retaining only elements that can extend to full solutions.
The mechanism: when searching for cycles and chains of transplants, the algorithm builds partial solutions incrementally. At each step, many partial solutions are equivalent in the sense that they can extend to the same completions. The representative set technique identifies and discards redundant partial solutions, keeping only a representative from each equivalence class. The compression is exponential — the number of representatives grows much slower than the number of partial solutions.
The resulting speedup is a factor of roughly 2 in the exponent, from O(14.34^t) to O(6.855^t). For t = 20, this is the difference between 10^23 and 10^16 operations — from infeasible to feasible.
What makes this work is that kidney exchange has the right algebraic structure for representative sets. The matroid intersection framework, originally developed for abstract combinatorial optimization, maps naturally onto the constraint that each donor gives exactly one kidney and each recipient receives exactly one. The biology and the algebra align. The problem doesn't get easier; the search gets smarter about what to ignore.