Please type your solution very clearly
- Theory Of Computation Please Type Your Solution Very Clearly 1 (203.65 KiB) Viewed 61 times
Theory of Computation. Please type your solution very clearly
-
answerhappygod
- Site Admin
- Posts: 899603
- Joined: Mon Aug 02, 2021 8:13 am
Theory of Computation. Please type your solution very clearly
Theory of Computation.
Please type your solution very clearly
3. Let. G = (V, E) be a graph. A vertex cover is a set of vertices C CV such that every edge in the graph touches one of the vertices in C. Here are some examples of vertex covers. Notice how every edge is adjacent to at least one red vertex. (a) (b) Formally, we will work with the following language VERTEX-COVER = {(G, k)|G is a graph that has a vertex cover of size k} In the textbook, Sipser proves that this language is NP-complete by giving a reduction from 3-SAT. We will give another proof that it is NP-complete by reducing from IND-SET. (a) (5 points) Prove that VERTEX-COVER E NP (Hint: create machine that either guess a vertex cover, or verifies that a proposed cover is valid and big enough) (b) (10 points) Prove that IND-SET Spoly VERTEX-COVER. This will prove that VERTEX-COVER is NP-Hard. Since we already proved that VERTEX-COVER E NP, this will establish that it is NP-complete. You may use without proof the fact that C is a vertex cover if and only if V\C is an independent set.
Please type your solution very clearly
3. Let. G = (V, E) be a graph. A vertex cover is a set of vertices C CV such that every edge in the graph touches one of the vertices in C. Here are some examples of vertex covers. Notice how every edge is adjacent to at least one red vertex. (a) (b) Formally, we will work with the following language VERTEX-COVER = {(G, k)|G is a graph that has a vertex cover of size k} In the textbook, Sipser proves that this language is NP-complete by giving a reduction from 3-SAT. We will give another proof that it is NP-complete by reducing from IND-SET. (a) (5 points) Prove that VERTEX-COVER E NP (Hint: create machine that either guess a vertex cover, or verifies that a proposed cover is valid and big enough) (b) (10 points) Prove that IND-SET Spoly VERTEX-COVER. This will prove that VERTEX-COVER is NP-Hard. Since we already proved that VERTEX-COVER E NP, this will establish that it is NP-complete. You may use without proof the fact that C is a vertex cover if and only if V\C is an independent set.