0
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ Jun 16, 2023 at 19:18
  • $\begingroup$ @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 $\endgroup$
    – Anuj
    Jun 17, 2023 at 0:42
  • $\begingroup$ 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 $\endgroup$
    – Anuj
    Jun 17, 2023 at 0:55
  • $\begingroup$ @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 $\endgroup$
    – Anuj
    Jun 17, 2023 at 1:07
  • $\begingroup$ 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. $\endgroup$ Jun 17, 2023 at 7:13

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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 . $\endgroup$
    – Anuj
    Jun 17, 2023 at 13:59
  • $\begingroup$ 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). $\endgroup$ Jun 17, 2023 at 14:08
  • $\begingroup$ 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 $\endgroup$
    – Anuj
    Jun 17, 2023 at 14:17
  • $\begingroup$ 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). $\endgroup$ Jun 17, 2023 at 15:03
  • $\begingroup$ yeah ,I'll do that $\endgroup$
    – Anuj
    Jun 17, 2023 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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