We got a reduction maximum independent set to MIS in a very dense graph, or alternatively negative monotone 2-CNF to MAX-ONEs with a formula with many clauses.
Let $G$ be graph of order $n$ and adjacency matrix $A$ and consider the reduction $k$-independent set to MAX-ONEs CNF $J$.
If $G$ has $k$-IS, then there will exist permutation matrix $P$ such that $B=P A P^{-1}=P A P^T$ has left upper block of $k$ by $k$ zeros.
Let $P$ by $n$ by $n$ matrix with entries 0/1 variables $x_1,...x_n^2$.
For each row and for each column of $P$ add to $J$ the CNF clauses $(-x_i,-x_j)$, that is at most one variable per row or column is $1$.
So far we don't add the constraints at least variable to be $1$ because MAX-ONEs will take care of this.
Let $B=P A P^T$. The entries of $B$ are quadratic polynomials with positive coefficients.
For $1\le i,j,\le k$, let $q=B[i,j]$. For each monomial $m=c_i x_i x_j$ of $q$ add the constraint $(-x_i,-x_j)$ since if both variables are $1$ the entry in the upper block won't be zero.
We claim that $J$ has solutions with $n$ ones iff $G$ has independent set of size $k$, since the ones will make $P$ permutation matrix and $B$ will have zero block.
Alternatively, make $G'$ graph with edges the clauses of $J$. it is of order $n^2$ and edges $n^C$ for $C \ge 3$.
$G'$ has independent set of size $n$ iff $G$ has IS of size $k$. Reduction maximum independent set to MIS in a very dense graph
The clauses of $J$ are also at least $n^3$.
Cubic graphs have IS $k \ge n/3$ and this gives $n^2/9$ zeros and each monomial $q$ has at least $n$ monomials.
Define the logarithmic density of graph $glog(G)=\frac{\log(|E(G)|}{\log(|V(G|)|}$.
What is lower bound for $glog(G')$ of this construction?
We believe very dense graphs might have easier complexity of IS, since complements of bounded degree graphs have few independent sets and adding large degree vertex to the IS deletes all neighbors, reducing the size.
What is the complexity of finding $n$-independent set in $G'$, possibly for some restricted graph classes?
We have experimental support and in our sagemath implementation, the running time was dominated by computing the matrix product.
