DPV Problem $8\mathrm{.}10(d,g).$ Proving NP$-$completeness by generalization. For each of the problems below, prove that it is NP$-$complete by showing that it is a generalization of some NP$-$complete problem we have seen in this chapter.

$($d$)$ DENSE SUBGRAPH: Given a graph and two integers a and $b,$ find a set of a vertices of $G$ such that there are at least $b$ edges between them.

$($g$)$ Reliable network: We are given two $nn$ matrices, i$.$e$.,$ a distance matrix $d_{ij}$ and a connectivity requirement matrix $r_{ij},$ as well as a budget $b$; our goal is to find a graph $G=(\{1,2,$dots,$n\},E)$ such that $(1)$ the total cost of all edges is $b$ or less and $(2)$ between any two distinct vertices i and $j$ there are $r_{ij}$ vertex$-$disjoint paths.

Note that vertex$-$disjoint paths are paths that do not share any common vertices.

$($Hint: Suppose that all $d_{ij}$ values are $1$ or $2,b=n,$ and all $r_{ij}$ values are $2.$ Which well$-$known NP$-$complete problem is this?$)$