Finding a b-matching that embeds the maximum number of edge pairs in a given set

Abstract Given a set of edge pairs in a complete bipartite graph, the objective of the maximum edge-pair embedding bipartite b -matching problem (MEEB b M) is to find a bipartite b -matching that includes the maximum number of these edge pairs. The original problem, known as the maximum edge-pair embedding bipartite matching, was demonstrated to be NP-hard and inapproximable by Nguyen et al. in 2021. Building on this, and being inspired by the optimization of reconfigurable networks, we extend the problem in this paper to consider b -matchings, with a focus on scenarios where the number of edge pairs per node is bounded. Let $$ k $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> represent the maximum number of edge pairs that can be incident on a single node. We prove that when $$k &gt; b$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mi>b</mml:mi> </mml:mrow> </mml:math> , the problem is NP-hard. For the case when $$b = 2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>b</mml:mi> <mml:mo>=</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> , we provide an exact algorithm for $$k = 1,2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> . Additionally, for any values of k and b , we provide a $$\Theta (k)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Θ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -approximation algorithm for this problem.