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?

5 points

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

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

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