Minimum color‐degree perfect b‐matchings

Networks, vol. 77, pp. 477–494

Abstract

Abstract The minimum color‐degree perfect b‐matching problem (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 ‐hard on bipartite graphs by a reduction from (3,B2)‐Sat, and conclude that there exists no (2 − ϵ)‐approximation algorithm unless . 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 treewidth.

Authors 4

1. Mariia Anapolska Aachen Lehrstuhl II für Mathematik

   RWTH Aachen University

   Affiliation as printed

   Lehrstuhl II für Mathematik RWTH Aachen University Aachen Germany

2. Christina Büsing corresponding Aachen Lehrstuhl II für Mathematik

   RWTH Aachen University

   Affiliation as printed

   Lehrstuhl II für Mathematik RWTH Aachen University Aachen Germany

3. Martin Comis corresponding Aachen Lehrstuhl II für Mathematik

   RWTH Aachen University

   Affiliation as printed

   Lehrstuhl II für Mathematik RWTH Aachen University Aachen Germany

4. Tabea Krabs Aachen Lehrstuhl II für Mathematik

   RWTH Aachen University

   Affiliation as printed

   Lehrstuhl II für Mathematik RWTH Aachen University Aachen Germany