Matchings and vertex cover
Kent Quanrud · 62:30
Vertex cover and maximum matching are dual packing/covering problems on general graphs, but their optima are not always equal: vertex cover is NP-hard (it is the complement of independent set), while maximum matching...