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?

Multiple choice

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

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

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