when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-81245
URL:

; ; ;

### Parameterized Algorithms and Kernels for Rainbow Matching

 pdf-format:

### 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+\sqrt{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*(2^k) and polynomial space. Here, we show how a result by Björklund et al. [JCSS, 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.

### BibTeX - Entry

@InProceedings{gupta_et_al:LIPIcs:2017:8124,
author =	{Sushmita Gupta and Sanjukta Roy and Saket Saurabh and Meirav Zehavi},
title =	{{Parameterized Algorithms and Kernels for Rainbow Matching}},
booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
pages =	{71:1--71:13},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-046-0},
ISSN =	{1868-8969},
year =	{2017},
volume =	{83},
editor =	{Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},