Implement VERTEX COVER; that is, given graph G and integer k, answer the question of whether or not there is a vertex cover of size k or less. Begin by using a brute-force algorithm that checks all...

Implement VERTEX COVER; that is, given graph G and integer k, answer the question of whether or not there is a vertex cover of size k or less. Begin by using a brute-force algorithm that checks all possible sets of vertices of size k to find an acceptable vertex cover, and measure the running time on a number of input graphs. Then try to reduce the running time through the use of any heuristics you can think of. Next, try to find approximate solutions to the problem in the sense of finding the smallest set of vertices that forms a vertex cover.