There is a reduction in Sipser\'s book \"Introduction to the theory of computati

Question

There is a reduction in Sipser's book "Introduction to the theory of computation" on page 286 from 3SAT to Hamiltonian path problem.

Is there a simpler reduction?

By simpler I mean a reduction that would be easier to understand (for students).

Is there a reduction that uses linear number of variables?

The reduction in Sipser uses O(kn) variables where k is the number of clauses and n is the number of variables. In other words, it is possible for the reduction to blow the size from s to O(s2). Is there a simple reduction where the size of the output of the reduction is linear in the size of its input?

If it is not possible, is there a reason? Would that imply an unknown result in complexity/algorithms?

Explanation / Answer

The number of vertices in the well-known reduction from 3SAT to directed Hamiltonian Path(dHAMPATH) can be easily reduced to O(n+k), where n is the number of variables and k is the number of clauses, therefore the size of the constructed graph instance is linear to the size of the original 3SAT instance.

In the original reduction, we have start vertex and end vertex, k vertices for clauses, n lists of length 4k for variables. The idea is that we don't have to construct list of length 4k for each variable, we can construct list according to the number that the variable appears in all the clauses. Since the total number of appearances of variables in clauses is 3k, it is O(n+k).

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.