2
$\begingroup$

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

Improve this question
$\endgroup$
0
2
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks. I don't understand replacing with cliques. Would you please give the transformed $K_4$ which is of independence number $1$? $\endgroup$
    – joro
    Dec 6 '20 at 11:24
  • $\begingroup$ 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}}$. $\endgroup$
    – Laakeri
    Dec 6 '20 at 16:22
  • $\begingroup$ I added question with exponent 2 and degree()>= n/2 and a Mathoverflow link for another construction. $\endgroup$
    – joro
    Dec 8 '20 at 13:37
  • $\begingroup$ 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. $\endgroup$
    – Laakeri
    Dec 8 '20 at 19:39
  • $\begingroup$ 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). $\endgroup$
    – Laakeri
    Dec 8 '20 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.