In the decision version of the minimum vertex cover problem in a bipartite…

2025

In the decision version of the minimum vertex cover problem in a bipartite graph, if the answer is "No", what serves as a valid No certificate?

Answer: A. A matching of size K + 1

  1. A.

    A matching of size K + 1

  2. B.

    A vertex cover of size K - 1

  3. C.

    An edge not included in the cover

  4. D.

    A subgraph with no matchings

Attempted by 80 students.

Show answer & explanation

Correct answer: A

Explore the full course: Mppsc Assistant Professor Computer Science Paper 2

Loading lesson…