How can I argue that $3\mathsf{SAT}\leq_p \mathsf{IndSet}$ is polynomial in time?

Question

Given the reduction $3\mathsf{SAT}\leq_p \mathsf{IndSet}$ as follows:

How can I argue that it's in polynomial time? I understand how the reduction works, but even though it appears rather trivial, I can't explain why it's efficient.

To place $\mathsf{IndSet}$ in $\mathsf{NP}$-Hard, we will show $3\mathsf{SAT}\leq_p \mathsf{IndSet}$:

Given $$\phi=\bigwedge_{m=1}^{n}(x_m\vee y_m\vee z_m)$$ with $m$ clauses, produce the graph $G_\phi$ that contains a triangle for each clause, with vertices of the triangle labeled by the literals of the clause. Add an edge between any two complementary literals from different triangles. Finally, set $k=m$. In our example, we have triangles on $x,y,\overline{z}$ and on $\overline{x},w,z$ plus the edges $(x,\overline{x})$ and $(\overline{z},z)$.

We need to prove two directions. First, if $\phi$ is satisfiable, then $G_\phi$ has an independent set of size at least $k$. Secondly, if $G_\phi$ has an independent set of size at least $k$, then $\phi$ is satisfiable. (Note that the latter is the contrapositive of the implication "if $\phi$ is not satisfiable, then $G_\phi$ does not have an independent set of size at least k".)

For the first direction, consider a satisfying assignment for $\phi$. Take one true literal from every clause, and put the corresponding graph vertex into a set $S$. Observe that $S$ is an independent set of size $k$ (where $k$ is the number of clauses in $\phi$).

For the other direction, take an independent set $S$ of size $k$ in $G_\phi$. Observe that $S$ contains exactly one vertex from each triangle (clause) , and that $S$ does not contain any conflicting pair of literals (such as $x$ and $\overline{x}$, since any such pair of conflicting literals are connected by an edge in $G_\phi$). Hence, we can assign the value True to all the literals corresponding with the vertices in the set $S$, and thereby satisfy the formula $\phi$.

This reduction is polynomial in time because $\Huge\dots?$

I've looked at many different examples of how this is done, and everything I find online includes everything in the proof except the argument of why this is polynomial. I presume it's being left out because it's trivial, but that doesn't help me when I'm trying to learn how to explain such things.

Answer 1

You are given a formula, and you will construct a graph. You can argue the reduction is polynomial time by analyzing the time you need to construct the graph. The transformation is an algorithm: write each step down, and analyze them. If every step takes polynomial time, you have shown the reduction runs in polynomial time.

Scan the clauses of the formula in time that is linear in the number of clauses. Scan the 3 literals in every clause. Build 3 vertices, with labels corresponding to the literals in a clause. This you can do in constant time, clearly. Once you have built a triangle, add it to your graph. With reasonable assumptions, you can do this in linear time, but details naturally depend on the way you represent your graph. Nevertheless, the time taken will be polynomial.

Finally, you only need to add edges between any two complementary literals from different triangles. Scan your triangles. For every literal in the triangle, scan through every other triangle, and see if there is a complementary triangle. If so, add an edge. This process takes polynomial time; for every triangle you are scanning every other triangle, so think of something quadratic. After every triangle has been scanned, $G_\phi$ has been built.