Bi-Weekly Talk: Martin Comis & Tabea Krabs: Minimum Color-Degree Perfect b -Matchings

Wednesday, July 10, 2019, 10:30am

Location: RWTH Aachen University, Department of Computer Science - Ahornstr. 55, building E3, room 9u10

Speaker: Martin Comis & Tabea Krabs

 

Abstract:

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.