Complexity of MAX-ONEs Monotone 2-SAT with $n^{3/2}$ or $C n^2$ clauses? Let $\phi$ be negative monotone 2-CNF on $n$ variables and $n^{3/2}$
clauses.
What is the complexity of finding satisfying assignment with maximum
number of ones $k$?
Alternatively let $G$ be a graph of order $n$ and $n^{3/2}$
edges. $G$ is dense.
What is the complexity of finding $k$-independent set of $G$?
Each variables $x_i$ is in about $\sqrt{n}$ clauses (alternatively
the degrees of vertices of $G$ are about $\sqrt{n}$).
Can we get fixed parameter tractable algorithm with parameter $k$?
Can we increase the exponent $3/2$ to get polynomial solutions?
If necessary assume $n$ is square to get rid of the fractions.
Added later
Third question:
Let $\frac12 \le C &lt; n$ and $d=Cn$. Let $G$ be $d$-regular graph.
It has $C n^2/2$ edges and each vertex has $d$ neighbors.
In CNF notation there are $C n^2/2$ clauses and each variable is in $d$
clauses.

Can we find MIS in $G$ in subexponential or polynomial time?

More details about this construction are on Mathoverlfow
In both questions the answer is the same for any exponent $1 &lt; \alpha &lt; 2$.
For the first question, we can use a degeneracy based algorithm to find an independent set of size $\Omega(\frac{n}{n^{\alpha-1}}) = \Omega(n^{2-\alpha})$ in polynomial time. Therefore we get an FPT algorithm for every constant $\alpha$ simply by outputting YES if $k &lt; c n^{2-\alpha}$ for some constant $c$, and otherwise solving the problem with bruteforce in $2^n = 2^{O(k^{1/(2-\alpha)})}$ time.
For the second question, we can prove that the problem is NP-hard for all $1 &lt; \alpha &lt; 2$ by reducing from maximum independent set problem in 3-regular graphs, which is NP-hard [1].
For some constant $\beta$ we make $n^\beta$ copies of each vertex, making the set of copies a clique for each vertex. Now the new graph has exactly the same maximum independent set as the old graph. It is $4 n^\beta - 1$ regular and has $n^{\beta+1}$ vertices, so we can choose $\beta \approx \frac{\alpha-1}{2-\alpha}$ to make it work for any $1 &lt; \alpha &lt; 2$.
[1] Garey, Michael R., David S. Johnson, and Larry Stockmeyer. &quot;Some simplified NP-complete problems.&quot; STOC 1974.