Matchings · Independent Sets

Lesson 2

Nikolai Chukhin · Alexander S. Kulikov

Problem. So, finding \(\alpha(G)\) for a given graph \(G\) is a computationally hard problem. Check your intuition: for which of the remaining three parameters (\(\alpha'\), \(\beta\), \(\beta'\)) do we know efficient algorithms?

This problem can only be submitted at Cogniterra.

  1. \(\alpha'(G)\) (maximum matching size)

  2. \(\beta(G)\) (minimum vertex cover size)

  3. \(\beta'(G)\) (minimum edge cover size)