Question

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.)

Short answer

3D MATCHING to SAT:

Consider the set of edges, and define variable s where true indicates that an edge is chosen. Create add clauses with the set of edges and variables without repeating the items more than once.

RUDRATA CYCLE to SAT:

Define the variables${\mathit{x}}_{ij}$from the hint, and achieve the requirements as that each vertex appears exactly once in the cycle. The neighbors in the cycle is connected by an edge.

Step-by-step solution

Explain 3D-MATCHING and RUDRATA CYCLE

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.

Step 2: Give a simple reduction from  3D  MATCHING to SAT

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.

Give a simple reduction from RUDRATA CYCLE to SAT

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.