Natural NP-complete problems with high density? (This question is related to a previous one, see the discussion in &quot;Almost easy&quot; NP-complete problems, but it may also be of independent interest, so I post it as a separate question.) 

Let us say that a language $L\subseteq \{0,1\}^*$ has high density, if it contains a positive constant fraction of all $n$-bit strings. That is, there is a constant $c&gt;0$, such that $$|L\cap \{0,1\}^n|\geq c2^n$$ holds for all $n$.

It is not hard to construct artificial examples of NP-complete problems with high density. For example, let $L$ be any NP-complete language. For a binary string $z$, let $w(z)$ denote the weight of $z$, which is the number of 1-bits in $z$. Now define 
$$ L'=\{xx\,|\,x\in L\}\cup \{y\,|\, w(y)\:\mbox{is odd}\}. $$
It is easy to see that $L'$ has high density, and it still remains NP-complete.

The above example, however, is quite artificial, it is constructed for the sole reason of exhibiting this property. I expected that one could easily find natural NP-complete problems with high density, and I was surprised that this turned out harder than I thought. So, the question is:


  What are some examples of natural NP-complete problems with high density?


Edit: 

From the discussion in the comments I realized that a better question would be this:


  What are some examples of natural NP-complete problems with the property that both the yes-instances and the no-instances have high density?
Comment => Answer.

In this paper, Posa shows that for some constant $c$, a graph chosen from the Erdos-Renyi random graph distribution $G(n, c \log n / n)$ has a Hamiltonian cycle with probability approaching $1$ as $n \rightarrow \infty$. If we encode the input to the Hamiltonian Cycle problem as simply a bit-string representing its adjacency matrix, the uniform distribution over $n$-vertex inputs would be exactly the $G(n,1/2)$ distribution (with some irrelevant self loops) -- much more dense than what's needed. Since the existence of a Hamiltonian cycle is a monotone property, the conclusion that the vast majority of graphs have a Hamiltonian cycle follows.



Possible approach to new question

My guess is that you get exactly that for the question of "does there exist a Hamiltonian cycle where $u$ is a neighbor of $v$". I'm not going to fully justify everything, but the reasoning may go roughly as follows. 

Claim: For $G \sim G(n,1/2)$ and $u$ and $v$ designated uniformly at random, there is a Hamiltonian path starting at $v$ and ending at $u$ with at least some constant probability.

Take a random Hamiltonian cycle (many of which will exist with overwhelming probability in $G(n,p)$). We show how to transform this, with at least constant probability of success, into a Hamiltonian Path with endpoints $u$ and $v$. For simplicity, we ignore (immediately fail on) the $o(1)$ fraction of cases in which $u$ and $v$ are a distance less than $4$ apart (thus, their neighborhoods are disjoint and not adjacent in the cycle). An intuitive guess is that the two neighbors of $v$ in this cycle should have an edge with constant probability (close to $1/2$), as should $v$ to one or both of the neighbors of $u$ (probability close to $3/4$). If all this happens (probability close to $3/8$), there is a Hamiltonian Path starting at $v$, heading to a neighbor of $u$, continuing along the original Hamiltonian path in the direction away from $u$ (skipping over $v$ once we get to that point), and finally ending at $u$. $\square$

Thus, with some constant probability $c$, there should be a Hamiltonian path starting at $v$ and ending at $u$. The chance that they're adjacent is $1/2$, so with probability $c/2 = \Omega(1)$, there is a Hamiltonian cycle in which $u$ is a neighbor of $v$. Conversely, with probability at least $1/2$ the vertices $u$ and $v$ are not adjacent, so there can't possibly be a Hamiltonian cycle with $u$ and $v$ as neighbors. The conclusion follows.