Hello Codeforces
Recently I have written tutorial talking about the Maximum Independent Set Problem in Bipartite Graphs. I have tried all my best to cover this problem, and explained some related problems: Minimum Vertex Cover (MVC), Maximum Cardinality Bipartite Matching (MCBM) and Kőnig’s Theorem. You can find the Tutorial in my website.
I am new to blog writing, so any feedback (positive and negative one) will be highly appropriated.
It's worth mentioning that $$$V_L \cup V_R$$$ and $$$U_L \cup U_R$$$ actually form the minimum cut of the graph as per Ford-Fulkerson theorem.
Ahhhh, I knew I would forget something, I will add it today.
I am pretty sure that we can have a better bound for Dinic's algo when running it on the flow graph that solves MCBM. The time complexity would be similar to Hopcroft Karp's algo.
Also, Edmond Karp's algo's time complexity will definitely be better on such flow graphs. Think about it, there are at most $$$\frac{n}{2} + 1$$$ iterations of BFS.
More than just similar complexity, Hopcroft-Karp is exactly Dinic's algorithm in a bipartite matching graph.
When I mentioned the time complexity I meant the worse case in a general graph. I will clarify it, thanks for pointing it out.
While a non-tight Big-O time complexity is technically correct due to definition of Big-O, I think it is nicer to give a tighter bound where possible.
e.g. if we have a line graph as our flow graph, surely we can see that any augmenting path algo will terminate in one pass right?