Minimum colored Maximum Matchings in vertex-colored Graphs
Johanne Cohen, Yannis Manoussakis, Jonas Sénizergues · HAL (Le Centre pour la Communication Scientifique Directe) · 2024
We deal with three aspects of the complexity of the problem of finding a maximum matching that minimizes the number of colors in a vertex-colored graph. We first prove that it isW[2]-hard with the number of color of the solution as parameter. Next that it is hard to approximate within logarithmic ratio of the number of internal nodes (nodes of degree 2 or more). And finally that it is fixed-parameter tractable with the size of a maximum matching as parameter.