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

PYQ MPPSC Assistant Professor 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?

  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 128 students.

Sign up free to check your answer

Sign up free

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

Loading lesson…