C137's blog

[Tutorial] Maximum Independent Set in Bipartite Graphs
By C137, history, 5 years ago, In English

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.

  • Vote: I like it
  • +76
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Ahhhh, I knew I would forget something, I will add it today.

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    More than just similar complexity, Hopcroft-Karp is exactly Dinic's algorithm in a bipartite matching graph.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    When I mentioned the time complexity I meant the worse case in a general graph. I will clarify it, thanks for pointing it out.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it

      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?

      → Reply