PROBLEM LINK:
Author: Roozbeh K
Tester: Roozbeh K
Editorialist: Roozbeh K
DIFFICULTY:
MEDIUM
PREREQUISITES:
Complexity theory, graph theory, graph data structures
PROBLEM:
This problem is the decision version of the vertex cover problem. The user has to determine if a vertex cover of size k exists or not.
QUICK EXPLANATION:
Vertex cover is an NP-complete problem, meaning there is no efficient algorithm to answer what the problem asks. However, since the constraints state that the size of the vertex cover (k) is small, we can come up with a clever algorithm to solve the problem in polynomial time (i.e. efficiently)
EXPLANATION:
The algorithm is described in detail in chapter 10.1 of Algorithm Design by Jon Kleinberg and Eva Tardos. The core idea is to choose an edge (say from vertex u to vertex v) and recursively verify that if we remove one of the nodes from the edge, the other node belongs to a smaller vertex cover. This algorithm can be implemented recursively or using a loop.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.