TheDeveloperBlog.com

Home | Contact Us

C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML

DAA | Subset-Sum Problem

DAA | Subset-Sum Problem with daa tutorial, introduction, Algorithm, Asymptotic Analysis, Control Structure, Recurrence, Master Method, Recursion Tree Method, Sorting Algorithm, Bubble Sort, Selection Sort, Insertion Sort, Binary Search, Merge Sort, Counting Sort, etc.

<< Back to DAA

Subset Cover

To Prove:-

  1. Subset Cover
  2. Vertex Cover ≤ρ Subset Cover
  3. Subset Cover≤ρ Vertex Cover
  4. Subset Cover ϵ NP

1) Subset Cover

Definition: - 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

Subset Cover 
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 Cover

In 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 Cover

Just for verification of the output perform the Reduction and create Clique and via an equation, N-K 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 Subset-Cover through Vertex Cover and Vertex Cover through Clique and to convert the decision-based 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 independent-set problem is to find a largest-size 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.

Subset Cover
Next TopicApproximation Algorithm




Related Links:

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

Related Links

Adjectives Ado Ai Android Angular Antonyms Apache Articles Asp Autocad Automata Aws Azure Basic Binary Bitcoin Blockchain C Cassandra Change Coa Computer Control Cpp Create Creating C-Sharp Cyber Daa Data Dbms Deletion Devops Difference Discrete Es6 Ethical Examples Features Firebase Flutter Fs Git Go Hbase History Hive Hiveql How Html Idioms Insertion Installing Ios Java Joomla Js Kafka Kali Laravel Logical Machine Matlab Matrix Mongodb Mysql One Opencv Oracle Ordering Os Pandas Php Pig Pl Postgresql Powershell Prepositions Program Python React Ruby Scala Selecting Selenium Sentence Seo Sharepoint Software Spellings Spotting Spring Sql Sqlite Sqoop Svn Swift Synonyms Talend Testng Types Uml Unity Vbnet Verbal Webdriver What Wpf