You are managing a network of computers. Every computer in this network needs to access a core database, which contains data necessary for basic operating system functions.

You can store a copy of the database in each computer, but this requires you to maintain all these copies. You can store just one copy in one specified computer, but then other computers need to request accesses through the network, which may cause considerable network congestion.

After some thought, you decide to select some computers from this network, such that they satisfy the following.

$1.$ You store a copy of the database on each of the selected computers.

$2.$ Each computer that is not selected has a direct link to at least one of the selected computers.

Now the question is$,$ can we select k computers such that the above criteria are satisfied?

$1.$ Formulate the above problem as a language $\backslash ($ L $\backslash )$ involving $\backslash (($G$,$ k$)\backslash )$ where $\backslash ($ G $\backslash )$ is a graph and $\backslash ($ k $\backslash )$ is a number.

$2.$ Prove that $\backslash ($ L $\backslash )$ is in NP$.$

$3.$ Prove that L is NP$-$hard.