<p>The <em>&quot;opposite&quot;</em> problem is affordable in linear time.</p>
<p>We have that each vertex <span class="math-container">$v$</span> shall be adjacent to all the vertices <span class="math-container">$u&gt;v$</span>, except for at most <span class="math-container">$3$</span> of them: this is precisely what the constraint <em>&quot;we must select at least <span class="math-container">$K_i - 3$</span> clasues from each set&quot;</em> is saying.</p>
<p>Now we scan all the vertices, from <span class="math-container">$v_1$</span> to <span class="math-container">$v_n$</span>: for each of them, we can either add it to the vertex cover or not. The crucial point here is that, the <strong>first time</strong> we decide to <strong>not</strong> add a certain <span class="math-container">$v_i$</span> to the vertex cover, all the other vertices <span class="math-container">$u &gt; v_i$</span> (except <span class="math-container">$3$</span> at most) must be added to it, leaving us with a residual, minuscule graph of at most <span class="math-container">$3$</span> 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.</p>
<p>After scanning all the vertices, we come out with <span class="math-container">$1 + n$</span> graphs: the empty graph (when you add all the <span class="math-container">$n$</span> vertices to the vertex cover), plus <span class="math-container">$n$</span> trivial graphs of at most <span class="math-container">$3$</span> vertices each (one such graph for each of the <span class="math-container">$n$</span> 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 <span class="math-container">$n$</span> trivial graphs, sum them all, add <span class="math-container">$1$</span>, and you have the vertex cover counting of the original graph.</p>
<p>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.</p>

CC BY-SA 4.0
2023-06-17T13:59:00.870Z
I don't understand your second para ,you said about adding vertices to vertex cover set but then you said that removing those vertices would us with a small set of at most 3 variables and then we can vertex cover of that one ,but even though we must select at least k-3 clauses from each set ,its not neccesary that there must be k-3 vertex in the vertex cover ,we might need only a few ,we have a choice to not select at-most 3 clauses from each .
Anuj
CC BY-SA 4.0
2023-06-17T14:08:44.337Z
If you do not include $v_i$ in the vertex cover, _all_ its _adjacent_ vertices $u > v_i$ _must be_ included in the vertex cover, because otherwise it would not be a vertex cover any longer (i.e. there would be at least one edge having both endpoints not included, thereby infringing the definition of vertex cover).
Giorgio Camerani
CC BY-SA 4.0
2023-06-17T14:17:37.740Z
But not all case will be like this , according to restriction ,there are 3 sets from which we can choose nothing as there lenghts are <=3 ,and the restriction also provides us with a choice that can create overlap between different sets ,thus we might not need to include all the vertices in vertex cover at all
Anuj
CC BY-SA 4.0
2023-06-17T15:03:17.687Z
All cases will be like that: as soon as you set a variabile to false for the first time, all the others are propagated to true, except at most 3. Those few small sets at the end do not change anything in the reasoning. Neither does the overlapping you mention. I invite you to try it out with pen and paper on some toy examples and, possibly, to code a software to generate your instances and submit them to some SAT solver / model counter (doing so you would be able to check yourself that each model has at most $4$ variables set to false).
Giorgio Camerani
CC BY-SA 4.0
2023-06-17T15:06:40.497Z
yeah ,I'll do that
Anuj
CC BY-SA 4.0
2023-06-22T12:57:05.870Z
Thanks for answering .
Anuj
CC BY-SA 4.0
2023-06-23T09:51:13.477Z
You're welcome.
Giorgio Camerani
CC BY-SA 4.0
2023-06-17T08:06:46.997Z
2023-06-17T08:15:02.643Z
2023-06-17T08:15:02.643Z
Giorgio Camerani
<p>In this <a href="https://cs.stackexchange.com/q/160621/157195">post</a> ,I introduced a new variant of #Positive-2-SAT .</p>
<blockquote>
<p>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:</p>
<ol>
<li><strong>A = [ ab ,ac ,ad ,ae ]</strong></li>
<li><strong>B = [ bc ,bd ,be ]</strong></li>
<li><strong>C = [ cd ,ce ]</strong></li>
<li><strong>D = [ de ]</strong></li>
</ol>
<p>Ex-</p>
<ol>
<li><p>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.</p>
</li>
<li><p>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.</p>
</li>
</ol>
</blockquote>
<p>The complexity status of this problem is still not known ,but we do know ,from this <a href="https://cstheory.stackexchange.com/a/14535/67865">post</a> ,that if we allow to choose at max only 3 clause from each set mentioned above  ,then this problem is #P-complete.</p>
<hr />
<p>I want to ask if this is #P-complete if we must select at least <strong>(K_i -3)</strong> 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 <strong>(k_i-3)</strong> clauses from each ,but its compulsary to select at least <strong>(k_i - 3)</strong> clauses from each set <em>[ A ,B ,C ,D ,....]</em>.</p>
<p>Here ,<strong>k_i</strong> is the lenght of each set :</p>
<p>Ex -</p>
<pre><code>k_A is length of set A 


k_B is the length of set B and so on. 
</code></pre>
<p>Each set has different length because of how they are defined in my post.</p>
<blockquote>
<p>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 <em>[ A ,B ,C ,D ,....]</em> ,and we know that, that problem is #P-complete ,thus I
was wondering if its &quot;opposite&quot; , where we must select at least <strong>(K_i
-3)</strong> clauses from each set <em>[A, B ,C ,D ,...]</em> is also #P-complete or not?</p>
</blockquote>

CC BY-SA 4.0
2023-06-16T19:18:28.343Z
Be careful, the _"choose max 3 clauses"_ property you mention is not the same as the 3-regularity property mentioned in the cited answer (e.g. your last vertex can be adjacent to all the other vertices). Thus it is not immediately obvious that your first problem is #P-complete (while I'm certain that it is $\oplus$P-complete). As for your second problem (the _"opposite"_), it is certainly not #P-complete as the resulting graph is almost equal to a clique (for which the number of vertex covers can be counted in linear time). By the way, I'm not the one who downvoted.
Giorgio Camerani
CC BY-SA 4.0
2023-06-17T00:42:44.900Z
@GiorgioCamerani Well the choose max 3 clause is not the same as 3-regular but its a superset thus as 3-regular version is #P-complete ,so is max-3 clause
Anuj
CC BY-SA 4.0
2023-06-17T00:55:45.400Z
Its not compulsary to choose any clause at all ,but the maximum amount of clauses you can choose from each is 3 -clauses ,thus it is enough to contain all the 3-regular cases as there is freedom to not-choose any clauses from any set too ,that will not lead to degree greater than 3, if degree is less than 3 we can always just choose a clause from the set
Anuj
CC BY-SA 4.0
2023-06-17T01:07:34.860Z
@GiorgioCamerani As for the second problem ,I don't undderstand how its almost a clcique ,I mean there is a choice to not select at most 3-clauses from each set ,thus it some sets ,we are free to not select anything as they don't have clauses greater than 3 ,thus its always possible to have graphs that are not almost cliques ,thus doesn't it make it harder for us count vertex covers for those -not-almost-cliques graphs and as the whole opposite problem is a super set ,thus its also hard to count vertex cover for this opposite problem
Anuj
CC BY-SA 4.0
2023-06-17T07:13:42.700Z
I should have written _"choose max r clauses"_ vs r-regularity to avoid confusion. When speaking about _"your first problem"_ I indeed meant the _"choose max 2 clauses"_ one (on which #P-completeness I'm less certain than on its $\oplus$P-completeness), but written as such I was admittedly misleading. So yes, of course _"choose max 3 clauses"_ is clearly #P-complete as it contains all 3-regular cases. While for the _"opposite"_ problem, I'm going to devote a dedicated answer to it.
Giorgio Camerani
CC BY-SA 4.0
2023-06-17T07:18:30.497Z
@GiorgioCamerani I look forward to it while I also try to solve it
Anuj
<cc.complexity-theory><counting-complexity><complexity>
Complexity of "opposite" version of a variant of #Positive-2-SAT
Anuj
# Complexity of "opposite" version of a variant of #Positive-2-SAT

(Asked by: username_0 on 2023-06-15)

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:

A = [ ab ,ac ,ad ,ae ]
B = [ bc ,bd ,be ]
C = [ cd ,ce ]
D = [ de ]

Ex-

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.

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?

**Tags:** cc.complexity-theory, counting-complexity, complexity
> **Comments:**
> **username_1**: Be careful, the _"choose max 3 clauses"_ property you mention is not the same as the 3-regularity property mentioned in the cited answer (e.g. your last vertex can be adjacent to all the other vertices). Thus it is not immediately obvious that your first problem is #P-complete (while I'm certain that it is $\oplus$P-complete). As for your second problem (the _"opposite"_), it is certainly not #P-complete as the resulting graph is almost equal to a clique (for which the number of vertex covers can be counted in linear time). By the way, I'm not the one who downvoted.  
> **username_0**: @GiorgioCamerani Well the choose max 3 clause is not the same as 3-regular but its a superset thus as 3-regular version is #P-complete ,so is max-3 clause  
> **username_0**: Its not compulsary to choose any clause at all ,but the maximum amount of clauses you can choose from each is 3 -clauses ,thus it is enough to contain all the 3-regular cases as there is freedom to not-choose any clauses from any set too ,that will not lead to degree greater than 3, if degree is less than 3 we can always just choose a clause from the set  
> **username_0**: @GiorgioCamerani As for the second problem ,I don't undderstand how its almost a clcique ,I mean there is a choice to not select at most 3-clauses from each set ,thus it some sets ,we are free to not select anything as they don't have clauses greater than 3 ,thus its always possible to have graphs that are not almost cliques ,thus doesn't it make it harder for us count vertex covers for those -not-almost-cliques graphs and as the whole opposite problem is a super set ,thus its also hard to count vertex cover for this opposite problem  
> **username_1**: I should have written _"choose max r clauses"_ vs r-regularity to avoid confusion. When speaking about _"your first problem"_ I indeed meant the _"choose max 2 clauses"_ one (on which #P-completeness I'm less certain than on its $\oplus$P-completeness), but written as such I was admittedly misleading. So yes, of course _"choose max 3 clauses"_ is clearly #P-complete as it contains all 3-regular cases. While for the _"opposite"_ problem, I'm going to devote a dedicated answer to it.  
> **username_0**: @GiorgioCamerani I look forward to it while I also try to solve it  

---

## 1 answers

### Answer by username_1 on 2023-06-17. Score: 0 | Accepted answer

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.

> **Comments:**
> **username_0**: I don't understand your second para ,you said about adding vertices to vertex cover set but then you said that removing those vertices would us with a small set of at most 3 variables and then we can vertex cover of that one ,but even though we must select at least k-3 clauses from each set ,its not neccesary that there must be k-3 vertex in the vertex cover ,we might need only a few ,we have a choice to not select at-most 3 clauses from each .  
> **username_1**: If you do not include $v_i$ in the vertex cover, _all_ its _adjacent_ vertices $u > v_i$ _must be_ included in the vertex cover, because otherwise it would not be a vertex cover any longer (i.e. there would be at least one edge having both endpoints not included, thereby infringing the definition of vertex cover).  
> **username_0**: But not all case will be like this , according to restriction ,there are 3 sets from which we can choose nothing as there lenghts are <=3 ,and the restriction also provides us with a choice that can create overlap between different sets ,thus we might not need to include all the vertices in vertex cover at all  
> **username_1**: All cases will be like that: as soon as you set a variabile to false for the first time, all the others are propagated to true, except at most 3. Those few small sets at the end do not change anything in the reasoning. Neither does the overlapping you mention. I invite you to try it out with pen and paper on some toy examples and, possibly, to code a software to generate your instances and submit them to some SAT solver / model counter (doing so you would be able to check yourself that each model has at most $4$ variables set to false).  
> **username_0**: yeah ,I'll do that  
> **username_0**: Thanks for answering .  
> **username_1**: You're welcome.  

---

