CSharp  Java  Python  Swift  GO  WPF  Ruby  Scala  F#  JavaScript  SQL  PHP  Angular  HTML
Subset CoverTo Prove:
1) Subset CoverDefinition:  Number of a subset of edges after making the union for a get all the edges of the complete graph G, and that is called Subset Cover. According to the graph G, which you have created the size of Subset Cover=2 v1{e1,e6} v2{e5,e2} v3{e2,e4,e6} v4{e1,e3,e5} v5{e4} v6{e3} v3Uv4= {e1, e2, e3, e4, e5, e6} complete set of edges after the union of vertices. 2) Vertex Cover ≤ρ Subset CoverIn a graph G of vertices N, if there exists a Vertex Cover of size k, then there must also exist a Subset Cover of size k even. If you can achieve after the Reduction from Vertex Cover to Subset Cover within a polynomial time, which means you did right. 3) Subset Cover ≤ρ Vertex CoverJust for verification of the output perform the Reduction and create Clique and via an equation, NK verifies the Clique also and through Clique you can quickly generate 3CNF and after solving the Boolean function of 3CNF in the polynomial time. You will get output. It means the output has been verified. 4) Subset Cover ϵ NP:Proof:  As you know very well, you can get the SubsetCover through Vertex Cover and Vertex Cover through Clique and to convert the decisionbased NP problem into Clique firstly you have to convert into3CNF and 3CNF into SAT and SAT into CIRCUIT SAT that comes from NP. Proof of NPC: The Reduction has been successfully made within the polynomial time form Vertex Cover to Subset Cover Output has also been verified within the polynomial time as you did in the above conversation so, concluded that SUBSET COVER also comes in NPC. Independent Set:An independent set of a graph G = (V, E) is a subset V'⊆V of vertices such that every edge in E is incident on at most one vertex in V.' The independentset problem is to find a largestsize independent set in G. It is not hard to find small independent sets, e.g., a small independent set is an individual node, but it is hard to find large independent sets.
Next TopicApproximation Algorithm
