5. (a) Formally define the decision problems Vertex Cover and Independent Set, explaining all tech- (2 marks) nical terms. b) Fix a positive integer k. Give a polynomial-time algorithm A for finding a vertex cover of (2 marks) size k in an input graph, or proving that none exists. (c) Describe an algorithm using A as a subroutine that solves the problem of finding the small- est vertex cover in a graph. What is the largest class of graphs for which this algorithm is (2 marks) guaranteed to run in polynomial time? Set (4 marks)