Optimization Online


Minimum Color-Degree Perfect b -Matchings

Mariia Anapolska (mariia.anapolska***at***rwth-aachen.de)
Christina Büsing (buesing***at***math2.rwth-aachen.de)
Martin Comis (comis***at***math2.rwth-aachen.de)
Tabea Krabs (krabs***at***math2.rwth-aachen.de)

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.

Keywords: b-matchings, bounded tree width, complexity, dynamic programming, edge-colored graphs, series-parallel graphs

Category 1: Combinatorial Optimization (Graphs and Matroids )

Category 2: Other Topics (Dynamic Programming )

Citation: Minimum Color-Degree Perfect b -Matchings, Lehrstuhl II für Mathematik, RWTH Aachen University, Pontdriesch 10–12, 52062 Aachen, Germany, 02/2019

Download: [PDF]

Entry Submitted: 02/14/2019
Entry Accepted: 02/15/2019
Entry Last Modified: 05/22/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society