Assignment

1. [Self-reducibility] Show how the optimization version of vertex cover problem is polynomial time-reducible to its decision version. The optimization version, known as min vertex cover problem, is this -- "given a graph G, find the minimum set of vertices that cover all the edges in G". The decision version is this -- "given a graph G and a constant k, is there a vertex cover of at most k vertices?" Here, we say a vertex "covers" an edge if and only if the vertex is an end-node of the edge.

2. [Polynomial-time reduction] Consider the construction of a graph (a.k.a. "gadget") studied in class when proving the polynomial-time reducibility 3-SAT ≤p INDEPENDENT-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.