Parameterized Algorithms and Kernels for Rainbow Matching

Abstract

In this paper, we study the NP-complete colorful variant of the classical MATCHING problem, namely, the RAINBOW MATCHING problem. Given an edge-colored graph G and a positive integer k, this problem asks whether there exists a matching of size at least k such that all the edges in the matching have distinct colors. We first develop a deterministic algorithm that solves RAINBOW MATCHING on paths in time O^⋆((1+√5/2)^k) and polynomial space. This algorithm is based on a curious combination of the method of bounded search trees and a “divide-and-conquer-like” approach, where the branching process is guided by the maintenance of an auxiliary bipartite graph where one side captures “divided-and-conquered” pieces of the path. Our second result is a randomized algorithm that solves RAINBOW MATCHING on general graphs in time O⋆(2k) and polynomial-space. Here, we show how a result by Björklund et al. (J Comput Syst Sci 87:119–139, 2017) can be invoked as a black box, wrapped by a probability-based analysis tailored to our problem. We also complement our two main results by designing kernels for RAINBOW MATCHING on general and bounded-degree graphs.