Back to Search
Start Over
Quadratic Vertex Kernel for Rainbow Matching.
- Source :
-
Algorithmica . Apr2020, Vol. 82 Issue 4, p881-897. 17p. - Publication Year :
- 2020
-
Abstract
- In this paper, we study the NP-complete colorful variant of the classic matching problem, namely, the Rainbow Matching problem. Given an edge-colored graph G and a positive integer k, the goal is to decide whether there exists a matching of size at least k such that the edges in the matching have distinct colors. Previously, in [MFCS'17], we studied this problem from the view point of Parameterized Complexity and gave efficient FPT algorithms as well as a quadratic kernel on paths. In this paper we design a quadratic vertex kernel for Rainbow Matching on general graphs; generalizing the earlier quadratic kernel on paths to general graphs. For our kernelization algorithm we combine a graph decomposition method with an application of expansion lemma. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRAPH coloring
*DECOMPOSITION method
*MATCHING theory
Subjects
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 82
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 141917039
- Full Text :
- https://doi.org/10.1007/s00453-019-00618-0