Problems remaining NP-complete for sparse or dense graphs

For each fixed pair α,c > 0 let INDEPENDENT SET (${\displaystyle m\le c{n}^{\alpha }}$) and INDEPENDENT SET (${\displaystyle m\ge (ⁿ₂)-c{n}^{\alpha }}$) be the problem INDEPENDENT SET restricted to graphs on n vertices with ${\displaystyle m\le c{n}^{\alpha }}$ or ${\displaystyle m\ge (ⁿ₂)-c{n}^{\alpha }}$ edges, respectively. Analogously, HAMILTONIAN CIRCUIT (${\displaystyle m\le n+c{n}^{\alpha }}$) and HAMILTONIAN PATH (${\displaystyle m\le n+c{n}^{\alpha }}$) are the problems HAMILTONIAN CIRCUIT and HAMILTONIAN PATH restricted to graphs with ${\displaystyle m\le n+c{n}^{\alpha }}$ edges. For each ϵ > 0 let HAMILTONIAN CIRCUIT (m ≥ (1 - ϵ)(ⁿ₂)) and HAMILTONIAN PATH (m ≥ (1 - ϵ)(ⁿ₂)) be the problems HAMILTONIAN CIRCUIT and HAMILTONIAN PATH restricted to graphs with m ≥ (1 - ϵ)(ⁿ₂) edges. We prove that these six restricted problems remain NP-complete. Finally, we consider sufficient conditions for a graph to have a Hamiltonian circuit. These conditions are based on degree sums and neighborhood unions of independent vertices, respectively. Lowering the required bounds the problem HAMILTONIAN CIRCUIT jumps from 'easy' to 'NP-complete'.