%% BioMed_Central_Tex_Template_v1.06
%% %
% bmc_article.tex ver: 1.06 %
% %
%%IMPORTANT: do not delete the first line of this template
%%It must be present to enable the BMC Submission system to
%%recognise this template!!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% %%
%% LaTeX template for BioMed Central %%
%% journal article submissions %%
%% %%
%% <8 June 2012> %%
%% %%
%% %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% %%
%% For instructions on how to fill out this Tex template %%
%% document please refer to Readme.html and the instructions for %%
%% authors page on the biomed central website %%
%% http://www.biomedcentral.com/info/authors/ %%
%% %%
%% Please do not use \input{...} to include other tex files. %%
%% Submit your LaTeX manuscript as one .tex document. %%
%% %%
%% All additional figures and files should be attached %%
%% separately and not embedded in the \TeX\ document itself. %%
%% %%
%% BioMed Central currently use the MikTex distribution of %%
%% TeX for Windows) of TeX and LaTeX. This is available from %%
%% http://www.miktex.org %%
%% %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% additional documentclass options:
% [doublespacing]
% [linenumbers] - put the line numbers on margins
%%% loading packages, author definitions
%\documentclass[twocolumn]{bmcart}% uncomment this for twocolumn layout and comment line below
\documentclass{bmcart}
\usepackage{amssymb}
\usepackage{algorithm}
\usepackage{algorithmicx}
%\usepackage{algorithm2e}
\usepackage{algpascal}
\usepackage{algpseudocode}
\usepackage{etoolbox}
\usepackage{extraplaceins}
\usepackage{natbib}
\usepackage{graphicx}
%\usepackage{epstopdf}
\usepackage{stfloats}
\usepackage{crop}
\usepackage{flushend}
\algnotext{EndFor}
\algnotext{EndIf}
\algnotext{EndWhile}
%%% Load packages
%\usepackage{amsthm,amsmath}
%\RequirePackage{natbib}
%\RequirePackage[authoryear]{natbib}% uncomment this for author-year bibliography
%\RequirePackage{hyperref}
\usepackage[utf8]{inputenc} %unicode support
%\usepackage[applemac]{inputenc} %applemac support if unicode package fails
%\usepackage[latin1]{inputenc} %UNIX support if unicode package fails
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% %%
%% If you wish to display your graphics for %%
%% your own use using includegraphic or %%
%% includegraphics, then comment out the %%
%% following two lines of code. %%
%% NB: These line *must* be included when %%
%% submitting to BMC. %%
%% All figure files must be submitted as %%
%% separate graphics through the BMC %%
%% submission process, not included in the %%
%% submitted article. %%
%% %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\includegraphic{}
\def\includegraphics{}
%%% Put your definitions there:
\startlocaldefs
\endlocaldefs
%%% Begin ...
\begin{document}
%%% Start of article front matter
\begin{frontmatter}
\begin{fmbox}
\dochead{Research}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% %%
%% Enter the title of your article here %%
%% %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{An $O(n^3)$ time algorithm for the maximum weight b-matching problem on bipartite graphs}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% %%
%% Enter the authors here %%
%% %%
%% Specify information, if available, %%
%% in the form: %%
%% ={,} %%
%% = %%
%% Comment or delete the keys which are %%
%% not used. Repeat \author command as much %%
%% as required. %%
%% %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\author[
addressref={aff1}, % id's of addresses, e.g. {aff1,aff2}
% id of corresponding address, if any
% noteref={n1}, % id's of article notes, if any
email={f.rajabialni@aut.ac.ir} % email address
]{\inits{FRA}\fnm{Fatemeh} \snm{Rajabi-Alni}}
\author[
addressref={aff1},
corref={aff1},
email={ar\_bagheri@aut.ac.ir}
]{\inits{ARB}\fnm{Alireza} \snm{Bagheri}}
\author[
addressref={aff2},
email={b\_minaei@iust.ac.ir}
]{\inits{BMB}\fnm{Behrouz} \snm{Minaei-Bidgoli}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% %%
%% Enter the authors' addresses here %%
%% %%
%% Repeat \address commands as much as %%
%% required. %%
%% %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\address[id=aff1]{% % unique id
\orgname{Department of Computer Engineering, Amirkabir University of Technology}, % university, etc
% \street{Waterloo Road}, %
%\postcode{} % post or zip code
\city{Tehran}, % city
\cny{Iran} % country
}
\address[id=aff2]{%
\orgname{Department of Computer Engineering, Iran University of Science and Technology},
%\street{D\"{u}sternbrooker Weg 20},
%\postcode{24105}
\city{Tehran}, % city
\cny{Iran} % country
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% %%
%% Enter short notes here %%
%% %%
%% Short notes will be after addresses %%
%% on first page. %%
%% %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{artnotes}
%\note{Sample of title note} % note to the article
%\note[id=n1]{Equal contributor} % note, connected to author
\end{artnotes}
\end{fmbox}% comment this for two column layout
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% %%
%% The Abstract begins here %%
%% %%
%% Please refer to the Instructions for %%
%% authors on http://www.biomedcentral.com %%
%% and include the section headings %%
%% accordingly for your article type. %%
%% %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{abstractbox}
\begin{abstract} % abstract
\parttitle{Background} A \textit{matching} between two sets $A$ and $B$ assigns some elements of $A$ to some elements of $B$. Finding the similarity between two sets of elements by advantage of the matching is widely used in computational biology for example in the contexts of genome-wide and sequencing association studies. Frequently, the capacities of the elements are limited. That is, the number of the elements that can be matched to each element should not exceed a given number.
\parttitle{Results} We use bipartite graphs to model relationships between pairs of objects. Given an undirected bipartite graph $G=(A \cup B, E)$, the \textit{b-matching} of $G$ matches each vertex $v$ in $A$ (resp. $B$) to at least $1$ and at most $b(v)$ vertices in $B$ (resp. $A$), where $b(v)$ denotes the capacity of $v$. We propose the first $O(n^3)$ time algorithm for finding the maximum weight b-matching of $G$, where $|A|+|B|=O(n)$.
\parttitle{Conclusions} The b-matching has been studied widely for the bipartite graphs with integer weight edges. But our algorithm is the first algorithm for the maximum (respectively minimum) b-matching problem with non positive real (respectively non negative real) edge weights.
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% %%
%% The keywords begin here %%
%% %%
%% Put each keyword in separate \kwd{}. %%
%% %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{keyword}
\kwd{Hungarian algorithm}
\kwd{Many to many matching}
\kwd{Limited capacity}
\kwd{Bipartite graphs}
\end{keyword}
% MSC classifications codes, if any
%\begin{keyword}[class=AMS]
%\kwd[Primary ]{}
%\kwd{}
%\kwd[; secondary ]{}
%\end{keyword}
\end{abstractbox}
%
%\end{fmbox}% uncomment this for twcolumn layout
\end{frontmatter}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% %%
%% The Main Body begins here %%
%% %%
%% Please refer to the instructions for %%
%% authors on: %%
%% http://www.biomedcentral.com/info/authors%%
%% and include the section headings %%
%% accordingly for your article type. %%
%% %%
%% See the Results and Discussion section %%
%% for details on how to create sub-sections%%
%% %%
%% use \cite{...} to cite references %%
%% \cite{koon} and %%
%% \cite{oreg,khar,zvai,xjon,schn,pond} %%
%% \nocite{smith,marg,hunn,advi,koha,mouse}%%
%% %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%% start of article main body
%
%%%%%%%%%%%%%%%%
%% Background %%
%%
\section*{Background}
Given two sets of objects $A$ and $B$, a \textit{matching} matches each object of $A$ (respectively $B$) to at least one object of $B$ (respectively $A$). The matching has many uses including computational biology and pattern recognition \cite{LoC,Song,Rubert}. We can represent the sets and their relations using a bipartite graph; for example one part can represent mutated gens and other part outlying gens \cite{Song}. Given a weighted bipartite graph $G=(A \cup B,E)$, a matching in $G$ is the set of the vertex disjoint edges $M \subseteq E$. The weight of the matching $M$ which is denoted by $W(M)$ is the sum of the weights of all the edges in $M$, hence $$W(M)=\sum_{e \in M}W(e),$$where $W(e)$ denotes the weight of the edge $e$.
A \textit {maximum weight matching} $MWM$ is a matching that for any other matching $M'$, we have $W(M') \le W(MWM)$.
A \textit{perfect matching} is a subset of edges $PM \subseteq E$ such that every vertex of $G$ is adjacent to exactly one edge of $PM$. The first polynomial time algorithm for computing the maximum weight perfect bipartite matching (MWPBM) is the basic Hungarian algorithm \cite{Kuhn,Munkres}. Then, Fredman et al. \cite{Fredman} solved it in $O(mn + n^2 \log n)$ time by implementing the Hungarian algorithm using fibonacci heaps. Later, other algorithms were developed for bipartite graphs with integer weights \cite{Gabow,Orlin}.
The \textit{capacity} of a vertex $v$ is the number of the vertices that can be matched to $v$, denoted by $b(v)$. We use $deg(v)$ to refer to the degree of the vertex $v$ in the matching. Given an undirected bipartite graph $G=(A\cup B,E)$, the \textit{b-matching} finds an edge set such that $1\leq deg(v)\leq b(v)$ for all $v \in A\cup B$.
In many applications the capacities of objects are limited. For example, consider a biological pattern $A$, called the \textit{target pattern}, as a set of points. When we want to find the target pattern $A$ in other set of points $B$, the number of the points of $A$ which can be matched to each point of $B$ is limited. Assume $|A|+|B|=n$ and $|E|=m$. The best known algorithm for the maximum weight b-matching problem has the time complexity of $O(W'\sqrt{\beta'}m)$ for integer edge weights \cite{Huang}, where $W'=\max_{e \in E}(W(e))$, and $\beta'=\sum_{v \in A\cup B}b(v)$. In this paper, we present an $O(n^3)$-time algorithm for the maximum weight b-matching problem for non-positive real weighted edges. Note that a maximum weight b-matching in $G$ with non-positive real edge weights $W(e)$ is a minimum weight b-matching in $G$ with non-negative real edge weights $F(e)=-W(e)$ for all $e \in E$. Our algorithm is an interesting one for example in dense graphs.
We first review the basic Hungarian algorithm and some preliminary definitions. Then, we present our new algorithm.
%\section {Preliminaries}
%\label{Preliminaries}
\section*{Methods}
\label{Preliminaries}
Let $G=(A \cup B,E)$ be a weighted bipartite graph such that $|A|=|B|=n$, $|E|=m$ and the edge weights are non-positive real values. A path with the edges alternating between the edges of the matching $M$ and $E-M$ is called an \textit{alternating path}. Each vertex $v$ that is incident to an edge in $M$ is called a \textit {matched vertex}; otherwise it is a \textit {free vertex}. An alternating path with two free endpoints is called an \textit {augmenting path}. Note that if the edges of an augmenting path that are in $M$ are replaced with the ones that are in $E-M$, an \textit {augmentation}, its size increases by $1$.
A \textit {vertex labeling} is a function $l: V \rightarrow \Bbb{R^-} \cup \{0\}$ with $V=A \cup B$ that assigns a non-positive real value as a label to each vertex $v \in V$.
A vertex labeling that in which $l(a)+l(b) \ge W(a,b)$ for all $a \in A$ and $b \in B$ is called a \textit {feasible labeling}, where $W(a,b)$ denotes the weight of the edge $(a,b)$. The equality graph of a feasible labeling $l$ is a graph $G=(V,E_l)$ such that $E_l=\{(a,b)\in E| l(a)+l(b)=W(a,b)\}$. The \textit {neighbors} of a vertex $u \in V$ are defined as $N_l(u)=\{v\in V| (v,u) \in E_l\}$. Consider a set of vertices $S \subseteq V$, the neighbors of $S$ are $N_l(S)=\bigcup_{u \in S} N_l(u)$.
\newtheorem{lemma}{Lemma}
\begin{lemma}
\label{lem1}
Consider a feasible labeling $l$ of an undirected bipartite graph $G=(A\cup B, E)$ and $S \subseteq A$ with $T=N_l(S)\neq B$, let
$$\alpha_l=\min_{a_i \in S, b_j \notin T}(l(a_i)+l(b_j)-W(a_i,b_j)).$$ If the labels of the vertices of $G$ are updated such that:
$$l'(v)=\left\{
\begin{array}{lr}
l(v)-\alpha_l & if \ v \in S
\\
l(v)+\alpha_l & if\ v \in T
\\
l(v) & Otherwise
\end{array}
\right.,$$
then $l'$ is a feasible labeling such that $E_l \subset E_{l'}$.
\end{lemma}
\noindent \textbf{Proof.} Obviously in the cases $(a \in S,b \in T)$, $(a \notin S,b \in T)$ and $(a \notin S,b \in T)$, we have:
$$l'(a)+l'(b)\ge l(a)+l(b)\ge W(a,b).$$
And for some vertices $a \in S,b \notin T$, we have
$$l'(a)+l'(b)=l(a)-\alpha_l+l(b)=W(a,b).$$
%%%\qed
\newtheorem{theorem}{Theorem}
\begin{theorem}
If $l$ is a feasible labeling and $M$ is a perfect matching in $E_l$, then $M$ is a max-weight matching \cite{Kuhn}.
\end{theorem}
\nobreak\textbf {Proof.} Suppose that $M'$ is a perfect matching in $G$, since each vertex is incident to exactly one edge of $M'$ we have:
$$W(M')=\sum_{(a,b) \in M'} W(a,b)\le \sum_{v \in (A \cup B)}l(v).$$ Thus, $\sum_{v \in (A \cup B)}l(v)$ is an upper bound for each perfect matching. Now assume that $M$ is a perfect matching in $E_l$:
$$W(M)=\sum_{e \in M}l(e)=\sum_{v \in (A \cup B)}l(v).$$
%\qed
\begin{lemma}
\label{maximum}
After each augmentation of a matching, the cost of the matching decreases.
\end{lemma}
\noindent \textbf{Proof.} Given an augmenting path $P$, two cases arise:
\begin{itemize}
\item $P=(p_1,p_2)$. According to non-positive real edge weights, this condition is trivial.
\item $P=(p_1,p_2,p_3,\dots,p_n)$ (see Figure~{\ref{fig:2}}). Note that \newline $W(p_i,p_{i+1})=l(p_i)+l(p_{i+1})$ for $i=1,2,\dots,n-1$, since all edges of an augmenting path are in $E_l$. Assume for a contradiction that the lemma is false, and thus \newline $W(p_1,p_2)+W(p_3,p_4)+\dots+W(p_{n-1},p_{n})>W(p_2,p_3)+W(p_4,p_5)+\dots+W(p_{n-2},p_{n-1}).$ So it holds that: \newline$l(p_1)+l(p_2)+\dots+l(p_n)>l(p_2)+l(p_3)+\dots+l(p_{n-1})$
and thus: $l(p_1)+l(p_n)>0.$ Note that both $p_1$ and $p_n$ are free, and according to the above feasible labeling we have $l(p_n)\leq0$ and $l(p_1)\le 0$. Contradiction.
\end{itemize}
%\qed
Now, we review the basic Hungarian algorithm which computes a MWPBM in an undirected bipartite graph $G=(A \cup B, E)$ with $|A|=|B|=n$ (see Algorithm \ref{BasicHungarian}). It is shown that the maximum weight matching problem in bipartite graphs can be reduced to the MWPBM problem and solved using the Hungarian algorithm in $O(n^3)$ time \citep{Eiter}.
%figure1
\algsetblock[Name]{Initial}{}{3}{1cm}
\alglanguage{pseudocode}
\begin{algorithm}
\caption{The Basic Hungarian algorithm(G)}
\label{BasicHungarian}
\begin{algorithmic}[1]
\Initial \Comment Find an initial feasible labeling $l$ and a matching $M$ in $E_l$
\State Let $l(b_j)=0$, for all $1 \le j \le n$
\State $l(a_i)=\max_{j=1}^n W(a_i,b_j)$ for all $1 \le i \le n$
\State $M= \emptyset$
\While {$M$ is not perfect}
\State Select a free vertex $a_i \in A$ and set $S = \{a_i\}$, $T=\emptyset$
\For{$j\gets 1$ to $n$}
\State $slack[j]=l(a_i)+l(b_j)-W(a_i,b_j)$
\EndFor
\Repeat
\If {$N_l(S)=T$}
\State $\alpha_l=\min_{b_j \notin T}slack[j]$
\State $Update(l)$ \Comment Update the labels according to Lemma \ref{lem1}
\ForAll {$b_j \notin T$}
\State $slack[j]=slack[j]-\alpha_l$
\EndFor
\EndIf
\State Select $u \in N_l (S)-T$
\If {$u$ is not free}\Comment ($u$ is matched to a vertex $z$, extend the alternating tree)
\State $S = S \cup \{z\},T = T \cup \{u\}$.
\For{$j\gets 1, n$}
\State $slack[j]=\min (l(z)+l(b_j)-W(z,b_j),slack[j])$
\EndFor
\EndIf
\Until {$u$ is free}
\State $Augment(M)$
\EndWhile
\State \Return $M$
\end{algorithmic}
\end{algorithm}
In lines 2 and 3 of Algorithm \ref{BasicHungarian}, the vertices of the input bipartite graph are labeled by a feasible labeling. $M$ is an initial matching which can be empty (line 4). In each iteration of the while loop of lines 5--21 the size of $M$ is increased by $1$, so it iterates at most $n$ times. Let $$slack[j]=\min_{a_i\in S}(l(a_i)+l(b_j)-W(a_i,b_j)),$$
by advantage of the array $slack[1..n]$, each iteration of the while loop can be run in $O(n^2)$ time.
The repeat loop of lines 9--20 runs at most $O(n)$ times until finding a free vertex $u$. In line 11, the value of $\alpha_l$ can be computed by:
$$\alpha_l=\min_{b_j \notin T}slack[j],$$
in $O(n)$ time. After computing $\alpha_l$, in line 12 the feasible labeling $l$ is updated such that $N_l(S) \neq T$. The values of the slacks must also be updated (lines 13--14):
$$for \ all\ b_j \notin T, slack[j]=slack[j]-\alpha_l.$$ A vertex $u \in N_l(S)-T$ is selected in line 15. Observe that if $u$ is not a free vertex, the alternating tree should be extended (lines 15--17). Note that in the repeat loop, an alternating tree, a tree with alternating paths, is constructed to find an augmenting path. Once a vertex is moved form $\bar S$ to $S$, the values of $skack[1..n]$ are updated (lines 18--19) in $O(n)$ time. At most $O(n)$ vertices are moved from $\bar S$ to $S$, so the repeat loop takes the total time of $O(n^2)$. Therefore, the time complexity of the basic Hungarian algorithm is $O(n^3)$.
\section*{Results and discussion}
\subsection*{The maximum weight b-matching algorithm on bipartite graphs}
\label{newalgorithms}
Let $G=(A \cup B,E)$ be a bipartite graph with non-positive real edge weights, where $A=\{a_1,a_2,\dots,a_s\}$ and $B=\{b_1,b_2,\dots,b_t\}$ such that $s+t=n$. Let $C_A=\{\alpha_1,\alpha_2,\dots,\alpha_s\}$ and $C_B=\{\beta_1,\beta_2,\dots,\beta_t\}$ denote the capacities of $A$ and $B$, respectively. Assume w.l.o.g that $t\geq s$. We present an $O(n^3)$ time algorithm for computing a maximum weight b-matching in $G=(A \cup B,E)$, where each vertex $a_i \in A$ must be matched to at least $1$ and at most ${\alpha }_i$ vertices in $B$, and each vertex $b_j \in B$ must be matched to at least $1$ and at most ${\beta }_j$ vertices in $A$ for all $1 \leq i \leq s$ and $1 \leq j \leq t$.
Firstly, we construct a bipartite graph $G'=(X \cup Y, E)$ with $X=A \cup A'$ and $Y=B \cup B'$ as follows (see Figure~{\ref{fig:1}}). Then, we run our algorithm on it.
In a \textit {complete connection} between two sets each element of one set is connected to the all elements of the other set. We show each set of the vertices by a rectangle and the complete connection between them by a line connecting the two corresponding rectangles.
Given $A= \{a_1, a_2, \dots, a_s\}$ and $B= \{b_1, b_2, \dots, b_t\}$, we construct a complete connection between $A$ and $B$ where the weight of $(a_i, b_j)$ is equal to the cost of matching the point $a_i$ to $b_j$ for all $1 \le i \le s$ and $1 \le j \le t$.
Let $B'_j=\{b'_{j1},b'_{j2}, \dots, b'_{j(\beta_j-1)}\}$ for $1 \le j \le t$, and $B'= \{B'_1, B'_2, \dots, B'_t\}$. Each vertex of $A$ is connected to the all vertices of $B'$ such that $$W(a_i,b'_{jk})=W(a_i,bj)$$ for all $1 \le k \le (\beta_j-1)$.
Let $A'_i=\{a'_{i1},a'_{i2}, \dots, a'_{i(\alpha_i-1)}\}$ for $1 \le i \le s$ and $A'= \{A'_1,A'_2, \dots, A'_s\}$, we also construct a complete connection between the sets $B$ and $A'$ such that $$W(a'_{ik},bj)=W(a_i,bj)$$ for all $1 \le k \le (\alpha_i-1)$.
%shekl2
Now, we modify the basic Hungarian algorithm to get a new algorithm, called $ModifiedHungarianAlg$ (see Algorithm \ref{ModifiedHungarian}). In the modified Hungarian algorithm, line 5 of Algorithm \ref{BasicHungarian} is changed; the while loop is iterated until matching the subset $A\subseteq X$. By Lemma \ref{maximum}, using $ModifiedHungarianAlg$, we get an optimal matching in which the vertices of $A$ are matched, but some vertices of $B$ might be free. The initialization step is also removed.
Our new algorithm consists of two steps (see Algorithm \ref{CMWBM}); in the first step the vertices of $A\subseteq X$ are matched, and in the second one the vertices of $B\subseteq Y$. We claim that by applying our algorithm on $G'$, $Maxweight\ b-matching \ Algorithm(G=(A \cup B,E))$, we get a maximum weight b-matching between $A$ and $B$.
\begin{enumerate}
\item \textbf {Step I.} Given an undirected bipartite graph $G'=(X\cup Y,E)$ with $X=A \cup A'$ and $Y=B \cup B'$, in this step we call the function $ModifiedHungarianAlg(G',A,M,l)$. It matches an arbitrary vertex of each $B'_j$ for all $j=\{1,2,\dots,t\}$ until there does not exist any unmatched vertex in $A\subseteq X$.
\item \textbf {Step II.} In this step, we call the function $ModifiedHungarianAlg(G',B,M,l)$. We use the final labels and slacks of the vertices in Step I, so the labels of the vertices are feasible labeling. We also use the output matching of Step I as the initial matching of Step II. Once all vertices of $B\subseteq Y$ are matched, this step terminates. Note that by Lemma \ref{maximum}, if we continue matching the vertices of $B'$ the cost decreases. For each $a_i\in A$ for $1\leq i\leq s$, there exists the set $\{a_i\} \cup A'_i$ in $G'$ with $\alpha_i$ vertices. Also there exist $\beta_j$ copies of each $b_j\in B$ in the set $\{b_j\} \cup B'_j$ in $G'$ for $1\leq j\leq t$. So, the capacities of the vertices of $A$ and $B$ are satisfied.
\end{enumerate}
\subsection* {Time complexity}
The while loop of lines 1--23 of $ModifiedHungarianAlg(G',A,M,l)$, called \textit{the main loop}, is iterated until all vertices of $A$ are matched to exactly one vertex of $B \cup B'$. Obviously, it iterates $O(n)$ times, since the number of the vertices of $A$ is $O(n)$. In the following, we show that each iteration of the main loop of $ModifiedHungarianAlg(G',A,M,l)$ is done in $O(n^2)$ time.
\newtheorem{Observation}{Observation}
\begin{Observation}
\label{labelsB'}
The labels of all free vertices $b'_{jk}\in B'_j$ are equal for all $1 \le k \le \beta_j-1$.
\end{Observation}
Initially, we have $l(b'_{jk})=0$ for all $1 \leq k \leq \beta_j-1$. The function $Update(l)$ updates the labels of all the vertices $b'_{jk}\in T$, i.e. all the vertices $b'_{jk}$ that have been matched to a vertex in $S$. Hence, all free vertices $b'_{jk}\in B'_j$ have equal labels for $1 \le k \le \beta_j-1$.
\begin{Observation}
\label{slackB'}
The values of the slacks of all free vertices $b'_{jk}\in B'_j$ are equal for all $1 \le k \le \beta_j-1$.
\end{Observation}
Observation \ref{labelsB'} implies that the values of the slacks of all free vertices $b'_{jk}\in B'_j$ with $1 \le k \le \beta_j-1$ are equal.
\algsetblock[Name]{Initial}{}{3}{1cm}
\alglanguage{pseudocode}
\begin{algorithm}
\caption{ModifiedHungarianAlg($G'=(X\cup Y,E)$,$A$,$M$,$l$)}
\label{ModifiedHungarian}
\begin{algorithmic}[1]
\While{$\{ u \in A| u \ is \ free\}\neq \emptyset$}
\State Select a free vertex $x_i \in A$ and set $S = \{x_i\}$, $T=\emptyset$
\State $B''=\emptyset$
\For{$j\gets 1$ to $|B|$}
\State Select a free vertex $v \in B'_j$
\State $B''=B'' \cup \{v\}$
\EndFor
\State Let $C$ be the set of matched vertices of $B'$
\State $Y'=B \cup C \cup B''$
\ForAll {$y_j \in Y'$}
\State $slack[j]=l(x_i)+l(y_j)-W(x_i,y_j)$
\EndFor
\Repeat
\If {$N_l(S)=T$}
\State $\alpha_l=\min_{y_j \in Y' -T}slack[j]$
\State $Update(l)$ \Comment Update the labels according to Lemma \ref{lem1}
\ForAll {$y_j \in Y'-T$}
\State $slack[j]=slack[j]-\alpha_l$
\EndFor
\EndIf
\State Select $u \in N_l (S)-T$
\If {$u$ is not free}\Comment ($u$ is matched to a vertex $z$, extend the alternating tree)
\State $S = S \cup \{z\},T = T \cup \{u\}$.
\ForAll {$y_j \in Y'$}
\State $slack[j]=\min (l(z)+l(y_j)-W(z,y_j),slack[j])$
\EndFor
\EndIf
\Until {$u$ is free}
\State $Augment(M)$
\EndWhile
\State \Return $M$ and $l$
\end{algorithmic}
\end{algorithm}
\algsetblock[Name]{Initialize}{}{4}{1cm}
\alglanguage{pseudocode}
%\vspace{1cm}
\begin{algorithm}
\caption{Maxweight b-matching Algorithm($G=(A \cup B,E)$)}
\label{CMWBM}
\begin{algorithmic}[1]
\State Construct the bipartite graph $G'=(X\cup Y,E')$ from $G$ with $X=A \cup A'$ and $Y=B \cup B'$
%\State Find an initial feasible labeling $l$ and an initial matching $M$ in $E_l$
\Initial \Comment Find an initial feasible labeling $l$ and a matching $M$ in $E_l$
\State Let $p=|X|$, $q=|Y|$
\State Let $l(y_j)=0$ for all $1 \le j \le q$, and let $l(x_i)=\max_{j=1}^q W(x_i,y_j)$ for all $1 \le i \le p$
\State $M= \emptyset$
\State $(M,l)=$\Call{ModifiedHungarianAlg}{$G'$,$A$,$M$,$l$}
\State $(M,l)=$\Call{ModifiedHungarianAlg}{$G'$,$B$,$M$,$l$}
\State \Return $M$
\end{algorithmic}
\end{algorithm}
Note that the vertices of $B'_j$ are copies of a single vertex, i.e. $b_j$. By Observations \ref{labelsB'} and \ref{slackB'}, all free vertices of $B'_j$ have equal labels and slacks, so in each iteration of the main loop, we consider only one of the free vertices $b'_{jk}\in B'_j$ for $1 \le k \le \beta_j-1$, arbitrarily. Actually, in each iteration of the main loop, all the free vertices $b'_{jk}\in B'_j$ are considered as a single vertex (line 7). Let $B''={b''_1,b''_2, \dots,b''_t}$, where $b''_j$ is an arbitrary free vertex of $B'_j$, if exists. Let $Y'=B \cup C \cup B''$, where $C$ is the set of the matched vertices of $B'$ with respect to $M$ (lines 7--8). In each iteration of the main loop, we first give the slacks of all vertices $y_j \in Y'$ initial values in $O(n)$ time (lines 9--10). Then the repeat loop of lines 11--22 is iterated until we find an augmenting path with the starting vertex $x_i$. Note that if $N_l(S)=T$, we can always update the labels of the vertices of $G'$ to get a new feasible labeling that in which $N_l(S)\neq T$. Notice that the neighbor set of a vertex $u \in A$ is defined as $N_l(u)=\{v \in Y'| (u,v) \in E_l\}$.
Note that there exist at most $O(n)$ matched vertices, i.e. the vertices of $A$, so the number of the vertices of $T$ and $S$ are at most $O(n)$ vertices. Hence, in line 13, we get the minimum value in $O(n)$ time. Also, updating the labels and slacks is done in $O(n)$ time (lines 14--16 and 20--21). As the first step, we can show that the time complexity of the second step is also $O(n^3)$. We observe that the values of the slacks and labels of all free vertices $a'_{ik}\in A'_j$ for all $1 \le k \le \alpha_i-1$ are equal.
\begin{Observation}
\label{slackA'}
The values of the slacks and labels of all free vertices $a'_{ik}\in A'_i$ are equal for all $1 \le k \le \alpha_i-1$.
\end{Observation}
\begin{theorem}
Let $G=(A \cup B,E)$ be a non-positive real weighted bipartite graph with $|A|+|B|=n$, a maximum weight b-matching in $G$ can be computed in $O(n^3)$ time.
\end{theorem}
\section*{Conclusions}
In this paper, we proposed an $O(n^3)$ time algorithm for finding a maximum weight b-matching in a bipartite graph $G=(A\cup B,E)$ with $|A|+|B|=n$, which can be used for example for computing the overall similarity of two given genomes. We modified the basic Hungarian algorithm and presented a new algorithm for a more general version of the matching problem. The b-matching problem has been studied widely in bipartite graphs with integer weight edges. But to the best of our knowledge, our algorithm is the first algorithm for the maximum weight b-matching problem in a bipartite graph with non positive real edge weights. In the future, we hope to develop new algorithms for other versions of the b-matching problem depending on the properties of two given input sets.%; for example when there are a given number of duplicates in two given genomes.
%\section*{Acknowledgements}
\begin{backmatter}
\section*{Abbreviations}
MWPBM: maximum weight perfect bipartite matching
\section*{Declarations}
\subsection*{Ethics approval and consent to participate}
Not applicable.
\subsection*{Consent to publish}
Not applicable.
\subsection*{Availability of data and materials}
Not applicable.
\subsection*{Competing interests}
The authors declare that they have no competing interests.
\subsection*{Funding}
Not applicable.
\subsection*{Authors' Contributions}
FR-A developed the theoretical results. FR-A, AB and BM-B discussed extensively about this study and analyzed the method. FR-A and AB wrote the manuscript. BM-B participated in revisiting the draft. All authors have read and approved the manuscript.
\subsection*{Acknowledgements}
The author would like to thank the referees for their careful reading of the paper and helpful comments.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% The Bibliography %%
%% %%
%% Bmc_mathpys.bst will be used to %%
%% create a .BBL file for submission. %%
%% After submission of the .TEX file, %%
%% you will be prompted to submit your .BBL file. %%
%% %%
%% %%
%% Note that the displayed Bibliography will not %%
%% necessarily be rendered by Latex exactly as specified %%
%% in the online Instructions for Authors. %%
%% %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% if your bibliography is in bibtex format, use those commands:
\bibliographystyle{bmc-mathphys} % Style BST file (bmc-mathphys, vancouver, spbasic).
\bibliography{bmc_article} % Bibliography file (usually '*.bib' )
% for author-year bibliography (bmc-mathphys or spbasic)
% a) write to bib file (bmc-mathphys only)
% @settings{label, options="nameyear"}
% b) uncomment next line
%\nocite{label}
% or include bibliography directly:
% \begin{thebibliography}
% \bibitem{b1}
% \end{thebibliography}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% %%
%% Figures %%
%% %%
%% NB: this is for captions and %%
%% Titles. All graphics must be %%
%% submitted separately and NOT %%
%% included in the Tex document %%
%% %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Do not use \listoffigures as most will included as separate files
\section*{Figures}
\begin{figure}[h!]
\vspace{-0.2cm}
\hspace{0cm}
\resizebox{1\textwidth}{!}{%
\includegraphics{figure1.png}
}
% If not, use
%\vspace{5cm} % Give the correct figure height in cm
\vspace{-0.5cm}
\caption{An example for illustration of Lemma \ref{maximum}; the hollow circles are free vertices and the filled circles are matched vertices.}
\label{fig:2} % Give a unique label
\end{figure}
\begin{figure}[h!]%[!tbp]
%\vspace{0cm}
\hspace{-0.4cm}
\resizebox{1\textwidth}{!}{%
\includegraphics{figure2.png}
}
% If not, use
\caption{Our constructed complete bipartite graph.}
%\vspace{5cm} % Give the correct figure height in cm
%\vspace{-0.9cm}
\label{fig:1} % Give a unique label
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% %%
%% Tables %%
%% %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Use of \listoftables is discouraged.
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% %%
%% Additional Files %%
%% %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section*{Additional Files}
\end{backmatter}
\end{document}