Exactly 1 in 3SAT (X3SAT) is a variation of the boolean satisfiability problem. Given a 3CNF instance is there a satisfying assignment where exactly one literal in each clause is true? X3SAT is known to be NP-Complete. It remains NP-Complete even if we only consider instances that are monotone and linear. Monotone means all of the literals are positive. Linear means no two clauses share more than one variable in common.

XSAT can be converted into a Maximum Weight Independent Set problem. Assign a vertex to each literal. There is an edge between two literals if they are together in a clause. There is an edge between a literal and its inverse. The weight for each literal is equal to the number of clauses containing that literal. The XSAT instance is satisfiable if and only if there exists an independent set with sum of weights equal to the number of clauses in the instance.

If $n$ is the number of variables in a monotone, linear X3SAT instance then the maximum number of clauses for $n$ is $O(n^2)$.

Let $m$ be the number of clauses in a linear, monotone X3SAT instance. There is only one instance each for $m=1, 2$. There are $3$ instances with $3$ clauses:

(a,b,c)(c,d,e)(e,f,g) - 3-chain

(a,b,c)(c,d,e)(a,d,f) - 3-loop

(a,b,c)(a,d,e)(a,f,g) - 3-star

So far, I have found $7$ different instances of monotone, linear X3SAT with $4$ clauses.

My question is how many how many distinct instances of monotone, linear X3SAT can there be with $m$ clauses? By distinct I mean ignore the ordering of the variables (vertices). Assume the instance is connected.

I posted this question on Computer Science and Kyle Jones pointed out the that the maximum number of connected graphs with $n$ vertices gives an upper bound to my question.

XSAT is NP-Complete for exact linear instances (not monotone). An instance is exact linear if any two clauses have exactly one variable in common. I would also be interested in how many exact linear X3SAT instances there are. Do these graphs belong to a known family of graphs?

  • $\begingroup$ Not really helpful but, terminology-wise, (connected) linear monotone X3SAT-instances correspond to (connected) linear 3-uniform hypergraphs. $\endgroup$ – Misha Lavrov Oct 20 '18 at 5:24

Your Answer

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

Browse other questions tagged or ask your own question.