I have a question, i was trying to reduce 3-SAT to a particular graph problem and i'm not quite sure about a thing i used in the reduction. In fact the reduction build a bipartite graph, the edge $(x_1,c_1)$ exist if the variable $x_1$ is in the clause number 1, the costs on that edge are dependent on the truthfulness of the variable $x_1$, cost 1 if $x_1$ is true and 0 elsewhere. My question :is it permitted in a reduction or should i have the entire graph instance independent from values taken by the variables ?

Thank you all!

  • $\begingroup$ More details (like what the graph problem is, and what your reduction is). Otherwise, this is a perfect fit for closure as "Not a Real Question". $\endgroup$
    – Aryabhata
    Apr 24 '13 at 23:00
  • $\begingroup$ I think that is a Real question and no need to detail more about the problem, my question is simple, when you reduce 3-sat to a problem X, could the instance of X be dependent on truthfulness of the variables or no ? $\endgroup$
    – madoc
    Apr 24 '13 at 23:07
  • $\begingroup$ Maybe it is just me, then. Good luck. $\endgroup$
    – Aryabhata
    Apr 24 '13 at 23:09
  • $\begingroup$ I tried to detail more the reduction, and i thank you anyway. $\endgroup$
    – madoc
    Apr 24 '13 at 23:13

If I understand your question correctly, you're asking whether you can construct a reduction where the truth assignment changes the construction.

In short, no. The whole point of a reduction from problem $A$ to problem $B$ is to show that we can solve $A$ using an algorithm for $B$ - if we already know the solution to $A$, then we could trivially reduce it to virtually any other problem.

In your particular case, if you already know the truth assignment to the variables, then you've already answered whether the input formula to the 3-SAT instance is satisfiable or not, what you want is a reduction that takes the formula, turns it into an instance of your graph problem, where solving the graph problem would tell you what to set the variables in the 3-SAT instance to.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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