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

Siraphob Buahong, Vorapong Suppakitpaisarn () and Piyashat Sripratak
Additional contact information
Siraphob Buahong: Chiang Mai University
Vorapong Suppakitpaisarn: The University of Tokyo
Piyashat Sripratak: Chiang Mai University

Journal of Combinatorial Optimization, 2025, vol. 49, issue 5, No 23, 15 pages

Abstract: Abstract 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.

Keywords: Quadratic Assignment; Approximation Algorithm; Computational Complexity; b-matching; 68W25: Approximation algorithms; 03D15: Complexity of computation; 68W40: Analysis of algorithms (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01305-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:49:y:2025:i:5:d:10.1007_s10878-025-01305-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01305-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().