C137's blog

By C137, history, 14 months ago,

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.

• +76

 » 14 months ago, # |   0 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.
•  » » 14 months ago, # ^ |   +8 Ahhhh, I knew I would forget something, I will add it today.
 » 14 months ago, # | ← Rev. 3 →   +10 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.
•  » » 14 months ago, # ^ |   0 More than just similar complexity, Hopcroft-Karp is exactly Dinic's algorithm in a bipartite matching graph.
•  » » 14 months ago, # ^ |   +8 When I mentioned the time complexity I meant the worse case in a general graph. I will clarify it, thanks for pointing it out.
•  » » » 14 months ago, # ^ | ← Rev. 3 →   +3 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?