21
$\begingroup$

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(s^2)$. 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?

Improve this question
$\endgroup$
8
  • $\begingroup$ Just to be clear: Do you want the reduction function that maps 3SAT instances to HP instances, or do you want the proof that reduces "3SAT in NPC?" to "HP in NPC?"? (I guess the first). Could you please outline the proof you refer to? Some of us might not have the book handy. $\endgroup$
    – Raphael ♦
    Mar 11, 2012 at 23:00
  • $\begingroup$ @Raphael, I want a reduction from 3SAT to HamPath. $\endgroup$
    – Kaveh
    Mar 11, 2012 at 23:07
  • $\begingroup$ The reduction in Sipser is long use gadgets, I prefer not to repeat the reduction here. You can interpret the first question as: is there a simple reduction? $\endgroup$
    – Kaveh
    Mar 11, 2012 at 23:11
  • 2
    $\begingroup$ @Kaveh I find the lecture slides here pretty easy to follow: cbcb.umd.edu/~carlk/bioinfo-lectures/sat.pdf They reduce 3sat to Ham. Cycle, and Ham. Cycle to Ham. Path. They were conveniently the first hit for "reduction from 3sat to hamiltonian path" but probably don't answer your second question. $\endgroup$
    – Joe
    Mar 12, 2012 at 0:15
  • 1
    $\begingroup$ @Kaveh: nice question, especially the "Would that imply an unknown result in complexity/algorithms?" part :-). I'm not an expert, but I would like to see it asked on cstheory. $\endgroup$
    – Vor
    Mar 25, 2012 at 17:35

1 Answer 1

Reset to default
8
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the nice reply. Could you provide some precise references, please? Thx. $\endgroup$
    – stegua
    Jan 12, 2022 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.