<p>In both questions the answer is the same for any exponent <span class="math-container">$1 &lt; \alpha &lt; 2$</span>.</p>
<p>For the first question, we can use a degeneracy based algorithm to find an independent set of size <span class="math-container">$\Omega(\frac{n}{n^{\alpha-1}}) = \Omega(n^{2-\alpha})$</span> in polynomial time. Therefore we get an FPT algorithm for every constant <span class="math-container">$\alpha$</span> simply by outputting YES if <span class="math-container">$k &lt; c n^{2-\alpha}$</span> for some constant <span class="math-container">$c$</span>, and otherwise solving the problem with bruteforce in <span class="math-container">$2^n = 2^{O(k^{1/(2-\alpha)})}$</span> time.</p>
<p>For the second question, we can prove that the problem is NP-hard for all <span class="math-container">$1 &lt; \alpha &lt; 2$</span> by reducing from maximum independent set problem in 3-regular graphs, which is NP-hard [1].
For some constant <span class="math-container">$\beta$</span> we make <span class="math-container">$n^\beta$</span> 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 <span class="math-container">$4 n^\beta - 1$</span> regular and has <span class="math-container">$n^{\beta+1}$</span> vertices, so we can choose <span class="math-container">$\beta \approx \frac{\alpha-1}{2-\alpha}$</span> to make it work for any <span class="math-container">$1 &lt; \alpha &lt; 2$</span>.</p>
<p>[1] Garey, Michael R., David S. Johnson, and Larry Stockmeyer. &quot;Some simplified NP-complete problems.&quot; STOC 1974.</p>

CC BY-SA 4.0
2020-12-06T11:24:19.143Z
Thanks. I don't understand replacing with cliques. Would you please give the transformed $K_4$ which is of independence number $1$?
joro
CC BY-SA 4.0
2020-12-06T16:22:32.733Z
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}}$.
Laakeri
CC BY-SA 4.0
2020-12-08T13:37:27.413Z
I added question with exponent 2 and degree()>= n/2 and a Mathoverflow link for another construction.
joro
CC BY-SA 4.0
2020-12-08T19:39:20.373Z
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.
Laakeri
CC BY-SA 4.0
2020-12-08T20:04:02.163Z
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 https://apps.dtic.mil/dtic/tr/fulltext/u2/a038864.pdf).
Laakeri
CC BY-SA 4.0
2020-12-09T09:23:24.043Z
Thanks for the paper! I edited the question asking for MIS for degree=Cn.
joro
CC BY-SA 4.0
2020-12-06T10:48:47.293Z
2020-12-06T10:54:56.113Z
2020-12-06T10:54:56.113Z
Laakeri
<p>Let <span class="math-container">$\phi$</span> be negative monotone 2-CNF on <span class="math-container">$n$</span> variables and <span class="math-container">$n^{3/2}$</span>
clauses.</p>
<p>What is the complexity of finding satisfying assignment with maximum
number of ones <span class="math-container">$k$</span>?</p>
<p>Alternatively let <span class="math-container">$G$</span> be a graph of order <span class="math-container">$n$</span> and <span class="math-container">$n^{3/2}$</span>
edges. <span class="math-container">$G$</span> is dense.</p>
<p>What is the complexity of finding <span class="math-container">$k$</span>-independent set of <span class="math-container">$G$</span>?</p>
<p>Each variables <span class="math-container">$x_i$</span> is in about <span class="math-container">$\sqrt{n}$</span> clauses (alternatively
the degrees of vertices of <span class="math-container">$G$</span> are about <span class="math-container">$\sqrt{n}$</span>).</p>
<p>Can we get fixed parameter tractable algorithm with parameter <span class="math-container">$k$</span>?</p>
<p>Can we increase the exponent <span class="math-container">$3/2$</span> to get polynomial solutions?</p>
<p>If necessary assume <span class="math-container">$n$</span> is square to get rid of the fractions.</p>
<p><strong>Added later</strong></p>
<p>Third question:</p>
<p>Let <span class="math-container">$\frac12 \le C &lt; n$</span> and <span class="math-container">$d=Cn$</span>. Let <span class="math-container">$G$</span> be <span class="math-container">$d$</span>-regular graph.
It has <span class="math-container">$C n^2/2$</span> edges and each vertex has <span class="math-container">$d$</span> neighbors.</p>
<p>In CNF notation there are <span class="math-container">$C n^2/2$</span> clauses and each variable is in <span class="math-container">$d$</span>
clauses.</p>
<blockquote>
<p>Can we find MIS in <span class="math-container">$G$</span> in subexponential or polynomial time?</p>
</blockquote>
<p>More details about this construction are on <a href="https://mathoverflow.net/questions/378429/conjecture-on-a-regular-graph-one-of-k-is-or-k-clique-is-at-most-subexponen">Mathoverlfow</a></p>

<cc.complexity-theory><graph-theory><sat>
Complexity of MAX-ONEs Monotone 2-SAT with $n^{3/2}$ or $C n^2$ clauses?
joro
# Complexity of MAX-ONEs Monotone 2-SAT with $n^{3/2}$ or $C n^2$ clauses?

(Asked by: username_0 on 2020-12-05)

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 < 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](https://mathoverflow.net/questions/378429/conjecture-on-a-regular-graph-one-of-k-is-or-k-clique-is-at-most-subexponen)

**Tags:** cc.complexity-theory, graph-theory, sat

---

## 1 answers

### Answer by username_1 on 2020-12-06. Score: 2

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.

> **Comments:**
> **username_0**: Thanks. I don't understand replacing with cliques. Would you please give the transformed $K_4$ which is of independence number $1$?  
> **username_1**: 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}}$.  
> **username_0**: I added question with exponent 2 and degree()>= n/2 and a Mathoverflow link for another construction.  
> **username_1**: 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.  
> **username_1**: 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 https://apps.dtic.mil/dtic/tr/fulltext/u2/a038864.pdf).  
> **username_0**: Thanks for the paper! I edited the question asking for MIS for degree=Cn.  

---

