DPV Problem $8\mathrm{.}13($a$-$d$).$ Determine which of the following problems are NP$-$complete

and which are solvable in polynomial time.

$($v$1\mathrm{.}1)$ If solvable in polynomial time, describe your algorithm; pseudo$-$code is not required,

but be sure your description is clear, concise, and precise. If NP$-$complete, describe $($clearly

and precisely$)$ the reduction from another NP$-$complete problem.

In each problem you are given an undirected graph G $=($V$,$ E$),$ along with:

$($a$)$ A set of nodes L $$ V $,$ and you must find a spanning tree such that its set of leaves

includes the set L$.$

$($b$)$ A set of nodes L $$ V $,$ and you must find a spanning tree such that its set of leaves is

precisely the set L$.$

$($c$)$ A set of nodes L $$ V $,$ and you must find a spanning tree such that its set of leaves is

included in the set L$.$

$($d$)$ An integer k$,$ and you must find a spanning tree with k or fewer leaves.

$5$