The minimum color-degree perfect b-matching roblem (Col-BM) is a new extension of the perfect b-matching problem to edge-colored graphs. The objective of Col-BM is to minimize the maximum number of differently colored edges in a perfect b-matching that are incident to the same node. We show that Col-BM is NP-hard on bipartite graphs by a reduction from (2B,3)-Sat, and conclude that there exists no (2-e)-approximation algorithm unless P = NP. However, we identify a class of two-colored complete bipartite graphs on which we can solve Col-BM in polynomial time. Furthermore, we use dynamic programming to devise polynomial-time algorithms solving Col-BM with a fixed number of colors on series-parallel graphs and simple graphs with bounded tree width.
Citation
Minimum Color-Degree Perfect b -Matchings, Lehrstuhl II für Mathematik, RWTH Aachen University, Pontdriesch 10–12, 52062 Aachen, Germany, 02/2019