# Reduction from 3-SAT to a graph problem

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!

• 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". – Aryabhata Apr 24 '13 at 23:00
• 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 ? – madoc Apr 24 '13 at 23:07
• Maybe it is just me, then. Good luck. – Aryabhata Apr 24 '13 at 23:09
• I tried to detail more the reduction, and i thank you anyway. – madoc Apr 24 '13 at 23:13

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.