Complexity of "opposite" version of a variant of #Positive-2-SAT

Question

In this post ,I introduced a new variant of #Positive-2-SAT .

This version of problem puts restrictions on the inputs of the #Positive-2-SAT such that we can only choose at max only 2 clauses from each set mentioned below to form our set of input clauses:

1. A = [ ab ,ac ,ad ,ae ]
2. B = [ bc ,bd ,be ]
3. C = [ cd ,ce ]
4. D = [ de ]

Ex-

1. A valid input to this variant of #Positive 2-SAT would be (ab ,ac ,bc ,cd) here we have only at max 2 clauses form each set mentioned above.

2. An invalid input to this variant of #Positive 2-SAT would be (ac ,ad ,ae ,bc ,cd) this is invalid as we have chosen more than 2 clauses from set A, mentioned above, thus its not a valid input to this version of the problem as we must only choose at max 2 clause form each set.

The complexity status of this problem is still not known ,but we do know ,from this post ,that if we allow to choose at max only 3 clause from each set mentioned above ,then this problem is #P-complete.

---

I want to ask if this is #P-complete if we must select at least (K_i -3) clasues from each set of clauses mentioned above to form our set of input clauses for this new variant of #Positive-2-SAT ,we can select more than (k_i-3) clauses from each ,but its compulsary to select at least (k_i - 3) clauses from each set [ A ,B ,C ,D ,....].

Here ,k_i is the lenght of each set :

Ex -

k_A is length of set A 


k_B is the length of set B and so on. 

Each set has different length because of how they are defined in my post.

My motivation for this problem is due to the fact that this problem is like opposite to the problem where we allowed to select only at max 3 clauses from each set [ A ,B ,C ,D ,....] ,and we know that, that problem is #P-complete ,thus I was wondering if its "opposite" , where we must select at least (K_i -3) clauses from each set [A, B ,C ,D ,...] is also #P-complete or not?

Answer 1

The "opposite" problem is affordable in linear time.

We have that each vertex $v$ shall be adjacent to all the vertices $u>v$, except for at most $3$ of them: this is precisely what the constraint "we must select at least $K_i - 3$ clasues from each set" is saying.

Now we scan all the vertices, from $v_1$ to $v_n$: for each of them, we can either add it to the vertex cover or not. The crucial point here is that, the first time we decide to not add a certain $v_i$ to the vertex cover, all the other vertices $u > v_i$ (except $3$ at most) must be added to it, leaving us with a residual, minuscule graph of at most $3$ vertices, for which the number of vertex covers can be counted in constant time. This is what I meant in my comment when saying that the graph induced by the above mentioned constraint would have been almost equal to a clique: as soon as you expel a vertex from the vertex cover under construction, the graph hugely simplifies in such a way that it becomes trivial.

After scanning all the vertices, we come out with $1 + n$ graphs: the empty graph (when you add all the $n$ vertices to the vertex cover), plus $n$ trivial graphs of at most $3$ vertices each (one such graph for each of the $n$ vertices that was the first expelled from the vertex cover). It is thus sufficient to count the number of vertex covers of each of the $n$ trivial graphs, sum them all, add $1$, and you have the vertex cover counting of the original graph.

In other words, the satisfying assignments of the input instance are allowed to have at most a constant number of variables set to false: this is the root cause that makes this problem easy.