Matchings · Independent Sets

Lesson 1

Nikolai Chukhin · Alexander S. Kulikov

Finding the maximum size of an independent set in a graph is a classic hard algorithmic problem. It is used to represent the Millennium Problem on the equality of complexity classes P and NP on the Clay Mathematics Institute website.