2. (25) [Polynomial-time reduction] Consider the construction of a graph (a.k.a. "gadget") studied in class when proving the polynomial-time reducibility 3-SAT SINDEPENDENT-SET. The construction steps are shown below 1. Add 3 vertices for each clause, one vertex for each literal. 2. Connect the 3 vertices in each triangle. 3. Connect the vertex of a literal and its negation between triangles. show that this construction take polynomial time. Assume a 3-SAT formula ? is given as a text string that is linearly parsed into literals and clauses. It is adequate to give an informal but accurate analysis of the construction running time complexity in big-O. If you will, however, feel free to actually write the construction algorithm in pseudocode to analyze the running time complexity. 2. (25) [Polynomial-time reduction] Consider the construction of a graph (a.k.a. "gadget") studied in class when proving the polynomial-time reducibility 3-SAT SINDEPENDENT-SET. The construction steps are shown below 1. Add 3 vertices for each clause, one vertex for each literal. 2. Connect the 3 vertices in each triangle. 3. Connect the vertex of a literal and its negation between triangles. show that this construction take polynomial time. Assume a 3-SAT formula ? is given as a text string that is linearly parsed into literals and clauses. It is adequate to give an informal but accurate analysis of the construction running time complexity in big-O. If you will, however, feel free to actually write the construction algorithm in pseudocode to analyze the running time complexity