3-Partition → Width-Two Two-Weight Fair Kidney Matching Complexity open
Unsolved
Why this question matters
Moderate: it would locate a sharp fairness-complexity boundary in country-partitioned two-way kidney exchange where matching itself is polynomial but choosing an optimally fair maximum-weight matching may not be.
Benedek et al. (Mathematical Programming 2025, Theorems 4–9 and Section 5) prove uniform weights tractable, two-weight hardness at unbounded width, and explicitly ask whether any fixed width and fixed number of weights suffice for hardness. Their Theorem 7 uses symmetric reciprocal arcs with two possible undirected edge totals. Width two and two edge totals is a fixed, inferred slice; its status is not separately asserted by the paper.
The reduction to construct
Input is a unary-encoded 3-Partition instance with 3m positive integers of total mB and each strictly between B/4 and B/2. Output YES exactly when they split into m triples of sum B; otherwise NO.
Input is an explicitly listed bidirected compatibility graph, positive binary rational arc weights such that each reciprocal pair has equal arc weights and the resulting undirected edge totals take at most two distinct values, a partition of vertices into countries of size at most two, a rational target utility vector x, and rational deviation bound D. Country utility is the sum of weights of incoming matched arcs at its vertices. Output YES exactly if some maximum-total-edge-weight matching has max-country absolute deviation from x at most D; otherwise NO.
Give polynomial-time F from 3-Partition and truth-preserving G with the width-two and two-weight restrictions intact. A positive reduction settles the NP-hard side of this exact kidney-exchange selection problem.
High: the 2025 two-weight hardness reduction uses unbounded country width to store unary item sizes. With width two, numerical choices must be distributed over many countries while preserving one global deviation constraint.
What a complete answer must include
Provide deterministic polynomial-time F and G with bit-size bounds. Prove correctness for every legal input and every valid target output, including NO-SOLUTION where defined; independently check recovered answers on representative instances. A generic SAT or ILP encoding alone does not meet the novelty goal.
References
Literature checked 2026-09-26. Web searches 2026-09-26: "width 2 2-sparse weakly close matching", "partitioned matching games fixed width sparse", and board aliases. Read 2025 definitions, Theorems 4–9 and Section 5. Theorem 9 relates another two-country three-weight slice to Exact Perfect Matching, so it does not settle this width-two, two-weight slice. Gate 5 route: replace each large country in Theorem 7 by a chain of width-two countries tied by utility targets; the unproved step is consistency across the chain. Untested; Gate 6 not assessed.