An O(n^3) time algorithm for the maximum-weight limited-capacity many-to-many matching in bipartite graphs

Articles in Press

Document Type : Original paper

Authors

School of Computer Engineering, Iran University of Science and Technology, Tehran, Iran

Abstract

Given an undirected bipartite graph $G=(A \cup B, E)$, a \textit {many-to-many matching} (MM) in $G$ matches each vertex $v$ in $A$ (resp. $B$) to at least one vertex in $B$ (resp. $A$). In this paper, we consider the \textit {limited-capacity many-to-many matching} (LCMM) in $G$, where each vertex $v\in A\cup B$ is matched to at least one and at most $Cap(v)$ vertices; the function $Cap : A\cup B \rightarrow \mathbb{Z}> 0$ denotes the capacity of $v$ (an upper bound on its degree in the LCMM). We give an $O(n^3)$ time algorithm for finding a maximum (respectively minimum) weight LCMM in $G$ with non-positive real (respectively non-negative real) edge weights, where $\lvert A \rvert+\lvert B \rvert=n$.

Keywords

Main Subjects

References

[1] L. Chen, R. Kyng, Y. Liu, R. Peng, M.P. Gutenberg, and S. Sachdeva, Maximum flow and minimum-cost flow in almost-linear time, J. ACM 72 (2025), no. 3, 1–103. https://doi.org/10.1145/3728631
[2] T.B. Eiter and H. Mannila, Distance measures for point sets and their computation, Acta Informatica 34 (1997), 109–133. https://doi.org/10.1007/s002360050075
[3] M.L. Fredman and R.E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, J. ACM 34 (1987), no. 3, 596–615. https://doi.org/10.1145/28869.28874
[4] H.N. Gabow, An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems, Proceedings of the fifteenth annual ACM symposium on Theory of computing, 1983, pp. 448–456.
[5] H.N. Gabow and R.E. Tarjan, Faster scaling algorithms for network problems, SIAM J. Comput. 18 (1989), no. 5, 1013–1036. https://doi.org/10.1137/0218069
[6] C.C. Huang and T. Kavitha, New algorithms for maximum weight matching and a decomposition theorem, Math. Oper. Res. 42 (2017), no. 2, 411–426. https://doi.org/10.1287/moor.2016.0806
[7] M. Imanparast and S.N. Hashemi, A linear time randomized approximation algorithm for Euclidean matching, J. Supercomput. 75 (2019), 2648–2664. https://doi.org/10.1007/s11227-018-2673-2
[8] H.W. Kuhn, The Hungarian method for the assignment problem, Nav. Res. Logist. Q. 2 (1955), no. 1-2, 83–97.
[9] C. Lo, S. Kim, S. Zakov, and V. Bafna, Evaluating genome architecture of a complex region via generalized bipartite matching, BMC Bioinformatics 14 (2013), #S13. https://doi.org/10.1186/1471-2105-14-S5-S13
[10] P.A.C. Lopes, S.S. Yadav, A. Ilic, and S.K. Patra, Fast block distributed CUDA implementation of the Hungarian algorithm, J. Parallel Distrib. Comput. 130 (2019), 50–62. https://doi.org/10.1016/j.jpdc.2019.03.014
[11] J Munkres, Algorithms for the assignment and transportation problems, J. Soc. Indust. Appl. Math 5 (1957), no. 1, 32–38.
[12] J.B. Orlin and R.K. Ahuja, New scaling algorithms for the assignment and minimum mean cycle problems, Math. Program. 56 (1992), 41–56. https://doi.org/10.1007/BF01586040
[13] D. Rubert, E. Hoshino, M. Braga, J. Stoye, and F. Martinez, Computing the family-free DCJ similarity, BMC Bioinformatics 19 (2018), 152. https://doi.org/10.1186/s12859-018-2130-5
[14] J. Song, W. Peng, and F. Wang, A random walk-based method to identify driver genes by integrating the subcellular localization and variation frequency into bipartite graph, BMC Bioinformatics 20 (2019), 238. https://doi.org/10.1186/s12859-019-2847-9
[15] Q. Zhang, H. Wang, Z. Feng, and Z. Han, Many-to-many matching-theory-based dynamic bandwidth allocation for UAVs, IEEE Internet Things J. 8 (2021), no. 12, 9995–10009. https://doi.org/10.1109/JIOT.2021.3049608
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 12 July 2026

Files

Share

How to cite

Statistics