Give a simple reduction from 3D MATCHING to SAT, and another from RUDRATA CYCLE to SAT.

(Hint: In the latter case you may use variables ${\mathit{x}}_{ij}$whose intuitive meaning is “vertex i is the j th vertex of the Hamilton cycle”; you then need to write clauses that express the constraints of the problem.)

Consider the three sets boys, girls and pets and the compatibilities among them are specified by a set of triples. 3D-MATHCING aims to find disjoint triples and creates harmonious households. RUDRATA CYCLE search problem is to find the cycle that visits each vertex only once or no such cycle exists.

Consider a set of m edges containing three items. If a set of edges is chosen in such a way that every item appears in an edge not in more than one edge, is called a valid matching.

Define variables$\left\{e_1,e_2,\mathrm{K},e_m\right\}$, in which the true indicates that an edge is chosen. Let x be a k-vector of indices in which the item appears.

Create the clauses as follows:

• Add clause$\left(e_{x_1}\vee e_{x_2}\vee \mathrm{K}{e}_{a_k}\right)$, ensures that the item appears at least once.

• For every pair $i,j\in \left\{1kk\right\}\text{add clause}\left(\overline{e_{x_i}}\vee \overline{e_{x_i}}\right)$, ensures that the item appearance is not be repeated.

Consider the variables ${\mathit{x}}_{ij}$that represents the vertex i is the j th vertex in the RUDRATA CYCLE. It is required that each vertex appears exactly once in the cycle and the neighbors in the cycle are connected by an edge.

Adding a clause $\left(x_{i1}\vee x_{i2}\vee K\vee x_{in}\right)$for each vertex i, ensures that appearance of the vertex exactly once in the cycle. Adding clauses for each pair of vertices for each cycle ensures that the neighbors are connected by an edge in the cycle. Construction of SAT involves the creation of role="math" localid="1657619324977" $n$clauses with $n$entries each plus $n^3$clauses with 2 entries each.

Therefore, the above reduction shows the reductions from RUDRATA CYCLE to SAT.