Bi-Weekly Talk: Martin Comis & Tabea Krabs: Minimum Color-Degree Perfect b -Matchings
Mittwoch, 10.07.2019, 10.30 Uhr
Ort: RWTH Aachen University, Informatikzentrum - Ahornstr. 55, Erweiterungsgebäude E3, Raum 9u10
Vortragende: Martin Comis & Tabea Krabs
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.