Harnessing the Power of Two Crossmatches

Kidney exchanges allow incompatible donor-patient pairs to swap kidneys, but each donation must pass three tests: blood, tissue, and crossmatch. In practice a matching is computed based on the first two tests, and then a single crossmatch test is performed for each matched patient. However, if two crossmatches could be performed per patient, in principle significantly more successful exchanges could take place. In this paper, we ask: If we were allowed to perform two crossmatches per patient, could we harness this additional power optimally and efficiently? Our main result is a polynomial time algorithm for this problem that almost surely computes optimal --- up to lower order terms --- solutions on random large kidney exchange instances.