Question in Theory of Computation - Admission/Application Essay Example

Unit Question in Theory of Computation In the given assignment, to demonstrate that VERTEX_COVER is in NP, we initially determine if the given graph has Vertex Cover of K nodes. Let us say there are a set of nodes, C of size K, and we want to prove they form a vertex cover. The proof that the set C is a vertex cover can be achieved in polynomial time. Another way for determining the attributes of the set is via examining the set by comparing the components of the adjacency matrix. This technique involves the consideration of columns and rows where one looks into the vertices or nodes of the graph and their adjacency to other vertices.

In this case example for, N – C, the nodes are not in the vertex cover. To illustrate on the above example, if each of these entries comprises of a 0, then, that means that there are no boundaries or edges in the graph, where both end points are not in C. Therefore, any edge in the graph ought to have at least a single end point that is in C. This confirms and proves that C is a vertex cover. Given that the amount of reviews that are required to establish this verification is (N-K)((N-K) = K2 -2KN + N2, and the time is polynomial in N and K, which is the magnitude of the problem.

Therefore, we can deduce that VERTEX_COVER is in NPShowing VERTEX_COVER is NP-CompleteThis is achieved via determining if NP-Complete problem can decrease to VERTEX_COVER, and his decrease takes polynomial time. The way of proving this is through utilizing an INDEPENDENT_SET proving how it will reduce to VERTEX_COVER. Considering the problem, that is, given a graph G with N nodes. The features to check if whether the graph has an independent set of size K, and figure out how to transform it into a VERTEX_COVER problem.

Determining if the graph G has a vertex cover of size C, whereby C = N – K, aids in defining This transformation utilizes the following principles:Principle followedReferring to the set of nodes of size K as the set KReferring to the set of nodes of size C as the set C.As you can deduce, these transformations can clearly be done in polynomial time. If the VERTEX_COVER has at least one node in set C. Therefore, concluding that there exist no edges where both end points are in set K, determining the set as an INDEPENDENT_SET.

If this was the opposite in the given Graph G, the answer would be ‘no’ for both the VERTEX_COVER and INDEPENDENT_SET. This therefore concludes that an INDEPENDENT_SET problem can be transformed into a VERTEX_COVER problem in polynomial time. This is proved in case if VERTEX_COVER says no, the INDEPENDENT_SET says no, and if VERTEX_COVER says yes, INDEPENDENT_SET says yes. This infers that INDEPENDENT_SET reduces to VERTX_COVER. Therefore, from the outcomes above, it can be specified that VERTEX_COVER is NP-Complete.

ReferencesBalakrishnan, R, and K Ranganathan. A Textbook of Graph Theory. , 2012. Print.Beineke, Lowell W, and Robin J. Wilson. Topics in Structural Graph Theory. New York: Cambridge University Press, 2013. Print.