Reduction from 3-SAT to a graphe problem

Question

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!

Answer 1

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.