Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2017.71
URN: urn:nbn:de:0030-drops-81245
URL: https://drops.dagstuhl.de/opus/volltexte/2017/8124/
Gupta, Sushmita ; Roy, Sanjukta ; Saurabh, Saket ; Zehavi, Meirav
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},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8124},
URN = {urn:nbn:de:0030-drops-81245},
doi = {10.4230/LIPIcs.MFCS.2017.71},
annote = {Keywords: Rainbow Matching, Parameterized Algorithm, Bounded Search Trees, Divide-and-Conquer, 3-Set Packing, 3-Dimensional Matching}
}
| Keywords: | Rainbow Matching, Parameterized Algorithm, Bounded Search Trees, Divide-and-Conquer, 3-Set Packing, 3-Dimensional Matching | |
| Seminar: | 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) | |
| Issue date: | 2017 | |
| Date of publication: | 01.12.2017 |
