The two-color budgeted matching problem: given a graph with red and blue edges, find a maximum matching with at most k red edges. This is polynomial-time solvable. Add a third color and the problem changes structurally.
Aprile and Di Summa study the three-color extension: edges are red, blue, or yellow, and the matching must contain specified quantities of each color while maximizing total cardinality. The polynomial-time algorithm they develop finds a matching satisfying the color requirements almost exactly and within 3 of optimal cardinality. Almost exactly — not exactly, and the gap of 3 is tight.
The method combines linear programming with analysis of restricted graph structures. On paths and cycles — the building blocks of matching theory — the three-color constraint creates interactions that two colors do not produce. Two-color constraints decompose cleanly because a path or cycle alternates between at most two states. Three colors break the alternation, requiring a different structural argument.
The proof invokes a topological property of plane curves that the authors describe as “curious.” The combinatorial problem — counting colored edges in a matching on paths — reduces to a geometric argument about how curves in the plane must intersect. The discrete matching structure and the continuous topological property speak to each other through the linear programming relaxation, which translates integer color constraints into geometric objects.
The structural lesson: each additional color is not an additive complication. Two colors are polynomial. Three colors are polynomial but with a constant approximation gap that two colors do not have. The combinatorial complexity does not scale linearly with the number of colors — it shifts qualitatively.
Correction (2026-11-06): I checked this essay against the raw arXiv abstract and parts of the text of Aprile and Di Summa, 'The red-blue-yellow matching problem' (2603.18754, v2). The abstract says the two-color red-blue matching problem has an unknown complexity status: a randomized polynomial-time algorithm exists but a deterministic one has been elusive for nearly four decades, and the best known deterministic approach (Yuster, 2012) is itself an additive approximation. So my first sentence that the two-color problem is polynomial-time solvable, and my conclusion that two colors are polynomial while three bring a constant gap that two do not, are wrong; the three-color result is described as 'a similar result' to the two-color one. The three-color algorithm also holds 'under natural assumptions'. The paper does show a bound is tight for odd paths (Remark 8, for its Theorem 6 on paths and cycles); I did not verify that the overall within-3 guarantee is tight, and the abstract does not say so. The closing claim that complexity 'shifts qualitatively' with each color is my own.