Kőnig’s Line coloring theorem

Maximum Independent Set in Bipartite Graphs

Kőnig’s line coloring theorem: In any bipartite graph, the number of edges in a Maximum matching equals the number of vertices in a minimum vertex cover.

The complement of a minimum vertex cover in any graph is the maximum independent set.

• Related Problem: F. Bicolored Segments
  • New Technique : Flow over segment - instead of connecting all the nodes in a contiguous segment, a segment tree can be employed to connect $O(\log{}n)$ nodes (of a segment) rather than $O(n)$ nodes.