The red-blue-yellow matching problem
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911717566447616 |
|---|---|
| author | Aprile, Manuel Di Summa, Marco |
| author_facet | Aprile, Manuel Di Summa, Marco |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_18754 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The red-blue-yellow matching problem Aprile, Manuel Di Summa, Marco Combinatorics Discrete Mathematics 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. |
| title | The red-blue-yellow matching problem |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2603.18754 |