# 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.

Third question:

Let $$\frac12 \le C < 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?

In both questions the answer is the same for any exponent $$1 < \alpha < 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 < 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 < \alpha < 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 < \alpha < 2$$.

[1] Garey, Michael R., David S. Johnson, and Larry Stockmeyer. "Some simplified NP-complete problems." STOC 1974.

• Thanks. I don't understand replacing with cliques. Would you please give the transformed $K_4$ which is of independence number $1$?
– joro
Dec 6, 2020 at 11:24
• The reduction replaces each vertex $v$ with a vertex set $X_v$ which is a clique and contains $n^{\beta}$ vertices. The neighbors of each $u \in X_v$ are $N(u) = X_v \setminus \{u\} \bigcup_{w \in N(v)} X_w$. So the graph $K_4$ transforms into $K_{4 n^{\beta}}$. Dec 6, 2020 at 16:22
• I added question with exponent 2 and degree()>= n/2 and a Mathoverflow link for another construction.
– joro
Dec 8, 2020 at 13:37
• I think it's against the rules to add more questions, but maybe I can try to answer if you write out what the question is (not just the definition of the graph). If the question if whether you can obtain a polynomial (or even subexponential) algorithm in this case I would bet the answer is NO. Dec 8, 2020 at 19:39
• By the way, for explaining your heuristic ideas and experiments, I would recommend the paper "Determining the stability number of a graph" of Chvatal (SICOMP 1977, preprint in apps.dtic.mil/dtic/tr/fulltext/u2/a038864.pdf). Dec 8, 2020 at 20:04