Problem $3(10$ points$)$ NP$-$completeness and reductions

Justify your answers for each of the following questions

$(2$ pts$)$ Explain the concept of polynomial$-$time reduction between two problems.

$(8pts)$ In the Vertex Cover decision problem, we are given as input a graph $G$ and a number $k,$ and we must

decide whether $G$ has a vertex cover with $k$ or fewer nodes. This problem is known to be NP$-$complete.

a$)(2pts)$ If Vertex Cover has no polynomial time solution $($that is if $PNP),$ can there exist a polynomial time

algorithm that takes as input a graph $G$ and finds the vertex cover of $G$ with the smallest number of vertices?

Why or why not?

b$)(2pts)$ If Vertex Cover has no polynomial time solution $($that is if $PNP),$ can there exist a polynomial time

algorithm that takes as input a graph $G$ and finds the vertex cover of $G$ with the largest number of vertices?

Why or why not?

c$)(2$ pts$)$ Given that Vertex Cover is NP$-$complete and the Maximum Flows $($MF$)$ problem can be solved in

polynomial time, is it likely that there's a reduction from Vertex Cover to SP$?$ What about the other way

around? Explain your answer.

d$)(2$ pts$)$ Consider three decision problems X$,$ Y$,$ Z where X$,$ Y $in$ NP and $Z$ is NP$-$complete. You are also

told that $xZ$ and $ZY.$ Place $x,Y$ in one of the classes $P,NP$ and NPC and justify your answer.