Post your solutions to the Apr 24 In-Class Exercise to this thread. Best, Chris

-- Apr 24 In-Class Exercise

'''Problem:''' For each @BT@n\ge0@BT@, give an example graph on @BT@n+1@BT@ vertices that has a vertex cover of size 1. @BT@@BT@ '''Solution:''' Let graph @BT@G@BT@ be a graph on @BT@n+1@BT@ vertices with a single edge. Let @BT@overline{G}@BT@ be the complement of @BT@G@BT@, i.e. @BT@G@BT@ will be a nearly complete graph missing just 1 edge. Therefore the @BT@\overline{G}@BT@ will have a clique of size @BT@n+1-1 = n@BT@. From our proof of vertex cover, if @BT@\overline{G}@BT@ has a clique of size @BT@n@BT@, then G has a vertex cover of size @BT@n+1-n = 1@BT@. @BT@@BT@ ---- @BT@@BT@ '''Problem:''' a @BT@p@BT@-time isomorphism is a @BT@p@BT@-time reduction which is one-to one and onto and whose inverse is @BT@p@BT@-time computable. Argue the reduction on the last slide is an isomorphism. @BT@@BT@ '''Solution:''' The complement of graph @BT@G@BT@ can be computed in polynomial time and is unique to any specific graph as the complement of a graph is bijective. We can prove this by contradiction by assuming graphs @BT@G1@BT@ and @BT@G2@BT@ to be distinct with the same complement @BT@\overline{G}@BT@. However, the complement of the complement @BT@G = \overline{\overline{G}}@BT@ is distinct and cannot be both @BT@G1@BT@ and @BT@G2@BT@, leading to a contraction. Therefore the complement is bijective. Because the complement can be found in polynomial time and is a bijection on the set of all graphs @BT@\mathbb{G}@BT@, the reduction relied on using the complement to find the clique and therefore is a @BT@p@BT@-time isomorphism. @BT@@BT@ ---- @BT@@BT@ '''Problem:''' What instances of CLIQUE would map to your graphs above? @BT@@BT@ '''Solution:''' All cliques of size @BT@n@BT@ for graphs on @BT@n+1@BT@ vertices.

-- Apr 24 In-Class Exercise

 For each n≥1, give an example graph on n+1 vertices that has a vertex cover of size 1.
 Construct the graph of n+1 vertices and select one vertex. Connect all other vertices to the selected vertex. The selected vertex is a vertex cover of size 1.

 A p-time isomorphism is a p-time reduction which is one-to-one and onto and whose inverse is p-time computable. Argue the reduction of the last slide is an p-time isomorphism.

 We can represent the graph as an adjacency matrix G (ignoring the diagonal since there are no self loop). We can compute the complement of G in polynomial time.  We can also compute |V| - k in polynomial time. The reduction is one to one and onto because the complement function is one to one and onto.

 What instances of CLIQUE would map to your graphs above?
 A graph with a CLIQUE of size n would map to the above graphs. All but the selected point would be in the clique.

For each n≥1, give an example graph on n+1 vertices that has a vertex cover of size 1. Construct the graph of n+1 vertices and select one vertex. Connect all other vertices to the selected vertex. The selected vertex is a vertex cover of size 1. A p-time isomorphism is a p-time reduction which is one-to-one and onto and whose inverse is p-time computable. Argue the reduction of the last slide is an p-time isomorphism. We can represent the graph as an adjacency matrix G (ignoring the diagonal since there are no self loop). We can compute the complement of G in polynomial time. We can also compute |V| - k in polynomial time. The reduction is one to one and onto because the complement function is one to one and onto. What instances of CLIQUE would map to your graphs above? A graph with a CLIQUE of size n would map to the above graphs. All but the selected point would be in the clique.

-- Apr 24 In-Class Exercise

A p-time isomorphism is a p-time reduction which is one-to-one and onto and whose inverse is p-time computable. Argue the reduction of the last slide is an p-time isomorphism. In order to show that the reduction of the VERTEX-COVER is p-time computable, we need to show that the graph is one-to-one which means that if x != y then f(x) != f(y) and we need to show onto which means for every y there exists x where y = f(x). In the example we state the graph has a number of verticies greater than 1. The VERTEX-COVER reduction means that every edge in the graph is covered. First the encoding of the graph needs to be stated. If the graph is encoded in an adjacency list. Then the encoded ordered pair includes the encoded representation of the graph and k. To show f(x) != f(y) we can show that given a graph of 5 verticies we can show that there exists a reduction and a clique. To show Onto the y would be the result of a reduction this can be shown with the 5 verticies graph stated previously which has a size of 1 as y would be a graph of 1 vertex.

-- Apr 24 In-Class Exercise

For each n≥1, give an example graph on n+1 vertices that has a vertex cover of size 1. Get a graph with n+1 vertices, choose one vertex and connect all of others to it. This vertex has cover of size 1. A p-time isomorphism is a p-time reduction which is one-to-one and onto and whose inverse is p-time computable. Argue the reduction of the last slide is an p-time isomorphism. The complement can be found in polynomial time and is a bijection on the set of all graphs G, the reduction relied on using the complement to find the clique, so it is a p-time isomorphism. What instances of CLIQUE would map to your graphs above? A CLIQUE with size n would map to the graphs above.

-- Apr 24 In-Class Exercise

For each n≥1, give an example graph on n+1 vertices that has a vertex cover of size 1. Create a graph with n+1 vertices, pick any vertex, connect all other vertices to this vertex. Then, by definition, we have a vertex cover of 1. A p-time isomorphism is a p-time reduction which is one-to-one and onto and whose inverse is p-time computable. Argue the reduction of the last slide is an p-time isomorphism. The complement of graph can be find in polynomial time. There is only one complement of a graph G, thus the complement of graph is a bijection on the set of all graphs. Since the it uses the complement of the graph to find clique, it is p-time isomorphism. What instances of CLIQUE would map to your graphs above? A clique of size n.

-- Apr 24 In-Class Exercise

1. From a graph with n+1 vertices, choose 1 vertex and draw edges from all other vertices to this vertex. This will form a graph with a vertex cover of size 1. 2. The complement of a graph can be found in polynomial time. It is a bijection on all graphs since each graph only has 1 complement. Thus the reduction is a p-time isomorphism. 3. A clique of size n including all vertices expect the selected vertex cover point would map to the graphs above.

-- Apr 24 In-Class Exercise

For each n≥1, give an example graph on n+1 vertices that has a vertex cover of size 1. A p-time isomorphism is a p-time reduction which is one-to-one and onto and whose inverse is p-time computable. Argue the reduction of the last slide is an p-time isomorphism. What instances of CLIQUE would map to your graphs above? For each n≥1, give an example graph on n+1 vertices that has a vertex cover of size 1. A p-time isomorphism is a p-time reduction which is one-to-one and onto and whose inverse is p-time computable. Argue the reduction of the last slide is an p-time isomorphism. We can represent the graph as an adjacency matrix G and compute the complement of G in polynomial time. It will be sovled in polynomial time. A clique graph of n size would map to the above graphs. All but the selected point would be in the clique.

-- Apr 24 In-Class Exercise

For each n≥1, give an example graph on n+1 vertices that has a vertex cover of size 1. ----> A graph G with n+1 vertices, with one vertex in the center connecting all the vertices around it but all other vertices are not interconnected. by definition of vertex cover, the size of vertex cover of G is 1. A p-time isomorphism is a p-time reduction which is one-to-one and onto and whose inverse is p-time computable. Argue the reduction of the last slide is an p-time isomorphism. ---->Only 1 component is in graph G, which can be completed in polynomial time. And since complement of graphs is used in order to find the clique, it is p-time isomorphism. What instances of CLIQUE would map to your graphs above? ----> A clique with size of will map to the graph above.

-- Apr 24 In-Class Exercise

 1)For each n≥1, give an example graph on n+1 vertices that has a vertex cover of size 1.

 2)A p-time isomorphism is a p-time reduction which is one-to-one and onto and whose inverse is p-time computable. Argue the reduction of the last slide is an p-time isomorphism.

 3)What instances of CLIQUE would map to your graphs above?

1)For each n≥1, give an example graph on n+1 vertices that has a vertex cover of size 1. Answer:-Construct a graph of n+1 vertices and select one vertex. Connect all other vertices to the selected vertex. The selected vertex is a vertex cover of size 1. 2)A p-time isomorphism is a p-time reduction which is one-to-one and onto and whose inverse is p-time computable. Argue the reduction of the last slide is an p-time isomorphism. Answer:-We can represent the graph as an adjacency matrix G (ignoring the diagonal since there are no self loop). We can compute the complement of G in polynomial time. We can also compute |V| - k in polynomial time. The reduction is one to one and onto because the complement function is one to one and onto. 3)What instances of CLIQUE would map to your graphs above? Answer:-A graph with a CLIQUE of size n would map to the above graphs. All but the selected point would be in the clique.