Abstract:We consider the red-blue-yellow matching problem: given two natural numbers $k_R$, $k_B$ and a graph $G$ whose edges are colored red, blue or yellow, the goal is to find a matching of $G$ that contains exactly $k_R$ red edges and exactly $k_B$ blue edges, and is of maximum cardinality subject to these constraints. This is a natural generalization of the well known red-blue matching problem, whose complexity status is unknown: although a randomized polynomial-time algorithm exists, a deterministic algorithm has remained elusive for nearly four decades. The best known deterministic approach to the red-blue matching problem, due to Yuster (2012), gives an additive approximation. In this paper, we show a similar result for the red-blue-yellow matching problem, giving a polynomial-time deterministic algorithm that, under natural assumptions, finds a matching satisfying the color requirements almost exactly and has cardinality within 3 of the optimal solution. Our algorithm is a mix of classic linear programming techniques and ad hoc existence results on restricted classes of graphs such as paths and cycles. As a key ingredient, we prove a curious topological property of plane curves, which is a strengthened version of a result by Grandoni and Zenklusen (2010) in the related context of budgeted matchings.
| Subjects: | Combinatorics (math.CO); Discrete Mathematics (cs.DM) |
| Cite as: | arXiv:2603.18754 [math.CO] |
| (or arXiv:2603.18754v2 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2603.18754 arXiv-issued DOI via DataCite |
|
| Related DOI: | https://doi.org/10.1016/j.disopt.2026.100956
DOI(s) linking to related resources |
From: Manuel Aprile [view email]
[v1]
Thu, 19 Mar 2026 11:02:34 UTC (48 KB)
[v2]
Mon, 25 May 2026 19:43:51 UTC (49 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。