Consider the following greedy algorithm for the Minimum Vertex Cover problem: In

Question

Consider the following greedy algorithm for the Minimum Vertex Cover problem:

Input G=(V,E)

C = emptyset;

while E is not equal to the emptyset

do

select the vertex v in V of maximum degree;

C = C union v;

Remove v from the graph and all of its edges.

done

return C;

a. (5 pts.) Explain how to implement this algorithm to make it as efficient as possible. (E.g., how are sets implemented, how are graphs implemented, etc.) Then, analyze the running time of this algorithm.

b. (5 pts.) Show that this algorithm always produces a vertex cover of the graph.

c. (5 pts.) Show that if this algorithm always produces the smallest vertex cover in any input graph, that P = NP.

Explanation / Answer

Algorithm: 1) Initialize result = {} 2) Let the set of all edges in given graph be E. 3) Do as follow untill E is not empty ...a) Pick an arbitrary edge (u, v) from set E and add 'u' and 'v' to result ...b) Eliminate all edges from set E that incident on either of u or v. 4) Return the result

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.