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.