Why is the time complexity of the following maximum bipartite matching implementation O(m*n^2)?

Question

There is this library that has implementations of many algorithms and one of them is maximum bipartite matching.

Here is the link to the source code: http://shygypsy.com/tools/bpm.cpp

I will include it here as well(without the comments)

#include <string.h>

#define M 128
#define N 128

bool graph[M][N];
bool seen[N];
int matchL[M], matchR[N];
int n, m;

bool bpm( int u )
 {
  for( int v = 0; v < n; v++ ) 
   if( graph[u][v] )
   {
    if( seen[v] ) continue;
    seen[v] = true;

    if( matchR[v] < 0 || bpm( matchR[v] ) )
    {
        matchL[u] = v;
        matchR[v] = u;
        return true;
    }
}
return false;
}

int main()
{
  memset( matchL, -1, sizeof( matchL ) );
  memset( matchR, -1, sizeof( matchR ) );
  int cnt = 0;
  for( int i = 0; i < m; i++ )
  {
      memset( seen, 0, sizeof( seen ) );
      if( bpm( i ) ) cnt++;
  }
  return 0;
}

We have a for loop that runs m times. The number m refers to the amount of workers. Then we enter the bpm function which has another for loop. This loop runs n times where n is the amount of tasks.

Until now we have m*n time complexity.

However there is a recursive function call of bpm in the third if statement. The goal of this function is to run a dfs in order to find an augmented path.

I know that dfs has a time complexity O(n+m). So I would assume that the function bpm has a complexity of O(n+m)

Thus the total time complexity would be O(m*(n+m))

However the author says it's O(m*n^2). Can someone explain me why is this the case? Thank you in advance!

Answer 1

The variables are somewhat confusing here: M and N refer to the number of nodes on each side of the graph. The runtime of DFS is O(E+V) where E is the number of edges. In a bipartite graph |E| is at most N*M and V will be (N+M), thus your DFS is going to take O(NM). The total time complexity is then O(NM^2). Not sure where the N^2 comes in, could be a typo...