This question has to do with self-reducibility. Show how the optimization versio

ID: 3109732 • Letter: T

Question

This question has to do with self-reducibility.

Show how the optimization version of vertex cover problem is polynomial time-reducible to its decision version.

The optimization version, known as min vertex cover problem, is this --

“given a graph G, find the minimum set of vertices that cover all the edges in G”.

The decision version is this --

“given a graph G and a constant k, is there a vertex cover of at most k vertices?”

Here, we say a vertex “covers” an edge if and only if the vertex is an end-node of the edge.

Consider the following solution of optimization version in terms of decision version:

for i = 1 to i = |V|

if there is a vertex cover of at most i vertices then return i

else increment i

This algorithm is linear reduction of optimization problem as for loop increases complexity by atmost(|V|) time.

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