Given a set of edge pairs in a complete bipartite graph, the objective of the maximum edge-pair embedding bipartite b-matching problem (MEEBbM) 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 <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1305_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">$ k $</EquationSource> <EquationSource Format="MATHML"><math> <mi>k</mi> </math></EquationSource> </InlineEquation> represent the maximum number of edge pairs that can be incident on a single node. We prove that when <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1305_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="44" /> </InlineMediaObject> <EquationSource Format="TEX">$k > b$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>></mo> <mi>b</mi> </mrow> </math></EquationSource> </InlineEquation>, the problem is NP-hard. For the case when <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1305_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">$b = 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>b</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, we provide an exact algorithm for <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1305_Article_IEq4.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="56" /> </InlineMediaObject> <EquationSource Format="TEX">$k = 1,2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>=</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>. Additionally, for any values of k and b, we provide a <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1305_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="36" /> </InlineMediaObject> <EquationSource Format="TEX">$\Theta (k)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-approximation algorithm for this problem.

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

期刊论文
出版模式：

开放获取
发表日期：

2025年6月2日

查看全文

Siraphob Buahong,
Vorapong Suppakitpaisarn,
Piyashat Sripratak

摘要

Given a set of edge pairs in a complete bipartite graph, the objective of the maximum edge-pair embedding bipartite b-matching problem (MEEBbM) 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 $ $k$ represent the maximum number of edge pairs that can be incident on a single node. We prove that when $k > b$ $k > b$ , the problem is NP-hard. For the case when $b = 2$ $b = 2$ , we provide an exact algorithm for $k = 1,2$ $k = 1, 2$ . Additionally, for any values of k and b, we provide a $\Theta (k)$ $Θ (k)$ -approximation algorithm for this problem.