Saeed Bakhshan and Maedeh Yahaghi , Wayne State University ,USA

A rainbow matching in an edge-colored graph is defined as a matching in which all edges have distinct colors. The maximum cardinality rainbow matching problem seeks to determine the largest rainbow matching in a graph. It is a fundamental problem in graph theory with numerous applications. In this paper, we present the first parallel approximation algorithm for rainbow matching in edge-colored bipartite graphs. This algorithm achieves a 1/3-approximation ratio, matching the classical guarantee for greedy maximal rainbow matchings (and, more generally, for 3-dimensional matching). Specifically, for any symmetric edge-colored bipartite graph with n vertices, m edges, and q colors, the proposed algorithm computes a maximal rainbow matching of size at least one third of the optimal matching in O(n) time on a PRAM with n2 processors. Additionally, we present a deterministic sequential version of the algorithm, which computes a 1/3-approximation in O(m + n log n) time, mirroring the approximation ratio of the parallel algorithm. We provide a practical OpenMP implementation of the proposed parallel algorithm on a multi-core system and perform an extensive performance evaluation. The experimental results show that for large graphs with hundreds of millions of edges, the parallel algorithm achieves a considerable speedup relative to its sequential counterpart of up to 5.908 when using 32 cores. Rainbow matchings naturally arise in data-intensive and machine learning workflows where we must select large sets of pairwise non-conflicting interactions (e.g., user-item, data-worker, or job-machine assignments) under diversity or fairness constraints represented as edge colors. We outline how the proposed sequential and parallel algorithms can serve as scalable combinatorial primitives for such tasks, while leaving a full empirical evaluation of downstream accuracy and fairness benefits to future work.

Rainbow matching , approximation algorithms , parallel algorithms , machine learning systems, graph-based learning