Questions tagged [2sat]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
51 views

Common solutions to 3SAT and 2SAT models comprised of the same variables

I have a problem which is a combination of 3SAT & 2SAT instances. Consider $L$ is a set of variables $(x_1 ... x_n)$. $S_3(L)$ is a 3-SAT instance and $S_2(L)$ is a 2SAT instance, both made of ...
1
vote
0answers
39 views

Find all paths between specially paired nodes in a DAG in linear time

If I have a DAG with 2n nodes partitioned into n pairs of nodes with e edges, is there a ...