Graph Theory37 sections · 1633 units
Open in Course

Maximum Independent Set

(Complement of vertex cover)

A maximum independent set is a largest set of vertices with no edges between them. In bipartite graphs, maximum independent set size equals Vmax matching|V| - \text{max matching} (by König's theorem and complement).

This is used in problems like selecting non-conflicting items or tasks. Compute max matching, then take all vertices not in the minimum vertex cover. These vertices form the maximum independent set.