## 3 Inapproximability of Densest At-Least-\(k\)-Subgraph  
We next prove our inapproximability result for Densest At-Least-\(k\)-Subgraph, which is also very simple. For this reduction and the subsequent reductions, it will be more convenient for us to use a different (but equivalent) formulation of SSEH. To state it, we first define a variant of SSE\((\delta,\eta)\) called SSE\((\delta,\eta,M)\); the completeness remains the same whereas the soundness is strengthened to include all \(S\) of size in \(\left[\frac{\delta|V|}{M},\delta|V|M\right]\). **Definition 2** (SSE\((\delta,\eta,M)\)). : _Given a regular edge-weighted graph \(G=(V,E,w)\), distinguish between:_  
* _(Completeness) There exists_ \(S\subseteq V\) _of size_ \(\delta|V|\) _such that_ \(\Phi(S)\leqslant\eta\)_._
* _(Soundness) For every_ \(S\subseteq V\) _with_ \(|S|\in\left[\frac{\delta|V|}{M},\delta|V|M\right]\)_,_ \(\Phi(S)\geqslant 1-\eta\)_._  
The new formulation of the hypothesis can now be stated as follows. **Conjecture 2**. : _For every \(\eta,M>0\), there is \(\delta=\delta(\eta,M)\in(0,1/2]\) such that SSE\((\delta,\eta,M)\) is NP-hard._  
[PERSON] et al. [11] showed that this formulation is equivalent to the earlier formulation (Conjecture 1); please refer to Appendix A.2 of [11] for a simple proof of this equivalence. Proof of Theorem 3.: Given an instance \(G=(V,E,w)\) of SSE\((\delta,\eta,M)\), we create an input graph \(G^{\prime}=(V^{\prime},w^{\prime})\) for Densest At-Least-\(k\)-Subgraph as follows. \(V^{\prime}\) consists of all the vertices in \(V\) and an additional vertex \(v^{*}\). The weight function \(w^{\prime}\) remains the same as \(w\) for all edges in \(V\) whereas \(v^{*}\) has only a self-loop with weight \(d\delta n/2\). (If we would like to avoid self-loops, we can replace \(v^{*}\) with two vertices \(v_{1}^{*},v_{2}^{*}\) with an edge of weight \(d\delta n/2\) between them.) In other words, \(E^{\prime}=E\cup\left\{(v^{*},v^{*})\right\}\) and \(w^{\prime}((v^{*},v^{*}))=d\delta n/2\). Finally, let \(k=1+\delta n\) where \(n=|V|\). **Completeness. ** If there is \(S\subseteq V\) of size \(\delta n\) such that \(\Phi(S)\leqslant\eta\), consider the set \(S^{\prime}=S\cup\{v^{*}\}\). We have \(|S^{\prime}|=k\) and the density of \(S^{\prime}\) is \(\left(d\delta n/2+E(S)\right)/k\) where \(E(S)\) denote the total weight of edges within \(S\). This can be written as\[\left(\frac{\delta n}{k}\right)\left(\frac{d\delta n/2+E(S)}{\delta n}\right)= \left(\frac{\delta n}{k}\right)\left(\frac{d}{2}+\left(\frac{1-\Phi(S)}{2} \right)d\right)\geqslant\frac{d\delta n(1-\eta/2)}{k}.\]  
**Soundness. ** Suppose that \(\Phi(S)\geqslant 1-\eta\) for every \(S\subseteq V\) of size \(|S|\in[\delta n/M,\delta nM]\). Consider any set \(T^{\prime}\subseteq V\) of size at least \(k\). Let \(T=T^{\prime}\setminus\{v^{*}\}\) and let \(E(T)\) denote the total weight of edges within \(T\). Observe that the density of \(S\) is at most \((d\delta n/2+E(T))/|T^{\prime}|\). Let us consider the following two cases. \(1.\) \(|T|\leqslant\delta nM\). In this case, \(\Phi(T)\geqslant 1-\eta\) and we have  
\[\frac{d\delta n/2+E(T)}{|T^{\prime}|}\leqslant\frac{d\delta n}{2k}+d\left( \frac{1-\Phi(T)}{2}\right)\leqslant\frac{d\delta n}{2k}+d\eta/2=\frac{d\delta n \left(\frac{1}{2}+\frac{\eta}{2}\left(1+\frac{1}{\delta n}\right)\right)}{k }\leqslant\frac{d\delta n(1/2+\eta)}{k}.\]  
2. \(|T|>\delta nM\). In this case, we have  
\[\frac{d\delta n/2+E(T)}{|T^{\prime}|}<\frac{d}{2M}+\frac{d}{2}=\frac{d\delta n }{k}\left(\frac{1}{2}+\frac{1}{2M}\right)\left(1+\frac{1}{\delta n}\right) \leqslant\frac{d\delta n\left(\frac{1}{2}+\frac{1}{\delta n}+\frac{1}{M} \right)}{k}.\]  
Hence, in both cases, the density of \(T^{\prime}\) is at most \(d\delta n\left(1/2+\max\{\eta,\frac{1}{\delta n}+\frac{1}{M}\}\right)/k\). For every sufficiently small constant \(\varepsilon>0\), by picking \(\eta=\varepsilon/20,M=40/\varepsilon\) and \(n\geqslant 800/(\varepsilon\delta)\), the ratio between the two cases is at least \((2-\varepsilon)\), concluding the proof of Theorem 3.