{"id":26538,"date":"2017-12-20T21:33:32","date_gmt":"2017-12-20T16:03:32","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26538"},"modified":"2017-12-20T21:33:32","modified_gmt":"2017-12-20T16:03:32","slug":"java-program-vertex-cover-problem-introduction-approximate-algorithm","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-program-vertex-cover-problem-introduction-approximate-algorithm\/","title":{"rendered":"java program &#8211; Vertex Cover Problem | Set 1 (Introduction and Approximate Algorithm)"},"content":{"rendered":"<p>A vertex cover of an undirected graph is a subset of its vertices such that for every edge (u, v) of the graph, either \u2018u\u2019 or \u2018v\u2019 is in vertex cover. <span id=\"more-132684\"><\/span>Although the name is Vertex Cover, the set covers all edges of the given graph. <em><strong>Given an undirected graph, the vertex cover problem is to find minimum size vertex cover<\/strong><\/em>.<\/p>\n<p>Following are some examples.<\/p>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Vertex_cover\" target=\"_blank\" rel=\"noopener noreferrer\">Vertex Cover Problem<\/a> is a known <a href=\"http:\/\/www.geeksforgeeks.org\/np-completeness-set-1\/\" target=\"_blank\" rel=\"noopener noreferrer\">NP Complete problem<\/a>, i.e., there is no polynomial time solution for this unless P = NP. There are approximate polynomial time algorithms to solve the problem though. Following is a simple approximate algorithm adapted from <a href=\"http:\/\/www.flipkart.com\/introduction-algorithms-english-3rd\/p\/itmdwxyrafdburzg?pid=9788120340077&affid=sandeepgfg\" target=\"_blank\" rel=\"noopener noreferrer\">CLRS book<\/a>.<\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>Approximate Algorithm for Vertex Cover:<\/strong><\/p>\n<pre>1) Initialize the result as {}\r\n2) Consider a set of all edges in given graph.  Let the set be E.\r\n3) Do following while E is not empty\r\n...a) Pick an arbitrary edge (u, v) from set E and add 'u' and 'v' to result\r\n...b) Remove all edges from E which are either incident on u or v.\r\n4) Return result \r\nFollowing diagram taken from <a href=\"http:\/\/www.flipkart.com\/introduction-algorithms-english-3rd\/p\/itmdwxyrafdburzg?pid=9788120340077&affid=sandeepgfg\" target=\"_blank\" rel=\"noopener noreferrer\">CLRS book<\/a> shows execution of above approximate algorithm.<\/pre>\n<p><strong>How well the above algorithm perform?<\/strong><br \/>\nIt can be proved that the above approximate algorithm never finds a vertex cover whose size is more than twice the size of minimum possible vertex cover (Refer <a href=\"http:\/\/www.personal.kent.edu\/~rmuhamma\/Algorithms\/MyAlgorithms\/AproxAlgor\/vertexCover.htm\" target=\"_blank\" rel=\"noopener noreferrer\">this <\/a>for proof)<\/p>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Vertex_cover\" target=\"_blank\" rel=\"noopener noreferrer\">Vertex Cover Problem<\/a> is a known <a href=\"http:\/\/www.geeksforgeeks.org\/np-completeness-set-1\/\" target=\"_blank\" rel=\"noopener noreferrer\">NP Complete problem<\/a>, i.e., there is no polynomial time solution for this unless P = NP. There are approximate polynomial time algorithms to solve the problem though. Following is a simple approximate algorithm adapted from <a href=\"http:\/\/www.flipkart.com\/introduction-algorithms-english-3rd\/p\/itmdwxyrafdburzg?pid=9788120340077&affid=sandeepgfg\" target=\"_blank\" rel=\"noopener noreferrer\">CLRS book<\/a>.<\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>Approximate Algorithm for Vertex Cover:<\/strong><\/p>\n<pre>1) Initialize the result as {}\r\n2) Consider a set of all edges in given graph.  Let the set be E.\r\n3) Do following while E is not empty\r\n...a) Pick an arbitrary edge (u, v) from set E and add 'u' and 'v' to result\r\n...b) Remove all edges from E which are either incident on u or v.\r\n4) Return result<\/pre>\n<p>Following diagram taken from <a href=\"http:\/\/www.flipkart.com\/introduction-algorithms-english-3rd\/p\/itmdwxyrafdburzg?pid=9788120340077&affid=sandeepgfg\" target=\"_blank\" rel=\"noopener noreferrer\">CLRS book<\/a> shows execution of above approximate algorithm.<\/p>\n<p><strong>How well the above algorithm perform?<\/strong><br \/>\nIt can be proved that the above approximate algorithm never finds a vertex cover whose size is more than twice the size of minimum possible vertex cover (Refer <a href=\"http:\/\/www.personal.kent.edu\/~rmuhamma\/Algorithms\/MyAlgorithms\/AproxAlgor\/vertexCover.htm\" target=\"_blank\" rel=\"noopener noreferrer\">this <\/a>for proof)<\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%2F%20Java%20Program%20to%20print%20Vertex%20Cover%20of%20a%20given%20undirected%20graph%0Aimport%20java.io.*%3B%0Aimport%20java.util.*%3B%0Aimport%20java.util.LinkedList%3B%0A%20%0A%2F%2F%20This%20class%20represents%20an%20undirected%20graph%20using%20adjacency%20list%0Aclass%20Graph%0A%7B%0A%20%20%20%20private%20int%20V%3B%20%20%20%2F%2F%20No.%20of%20vertices%0A%20%0A%20%20%20%20%2F%2F%20Array%20%20of%20lists%20for%20Adjacency%20List%20Representation%0A%20%20%20%20private%20LinkedList%3CInteger%3E%20adj%5B%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20Constructor%0A%20%20%20%20Graph(int%20v)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20V%20%3D%20v%3B%0A%20%20%20%20%20%20%20%20adj%20%3D%20new%20LinkedList%5Bv%5D%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cv%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%20%20%20%20adj%5Bi%5D%20%3D%20new%20LinkedList()%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2FFunction%20to%20add%20an%20edge%20into%20the%20graph%0A%20%20%20%20void%20addEdge(int%20v%2C%20int%20w)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20adj%5Bv%5D.add(w)%3B%20%20%2F%2F%20Add%20w%20to%20v\u2019s%20list.%0A%20%20%20%20%20%20%20%20adj%5Bw%5D.add(v)%3B%20%20%2F%2FGraph%20is%20undirected%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20The%20function%20to%20print%20vertex%20cover%0A%20%20%20%20void%20printVertexCover()%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Initialize%20all%20vertices%20as%20not%20visited.%0A%20%20%20%20%20%20%20%20boolean%20visited%5B%5D%20%3D%20new%20boolean%5BV%5D%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%3D0%3B%20i%3CV%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20visited%5Bi%5D%20%3D%20false%3B%0A%20%0A%20%20%20%20%20%20%20%20Iterator%3CInteger%3E%20i%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Consider%20all%20edges%20one%20by%20one%0A%20%20%20%20%20%20%20%20for%20(int%20u%3D0%3B%20u%3CV%3B%20u%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20An%20edge%20is%20only%20picked%20when%20both%20visited%5Bu%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20and%20visited%5Bv%5D%20are%20false%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(visited%5Bu%5D%20%3D%3D%20false)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Go%20through%20all%20adjacents%20of%20u%20and%20pick%20the%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20first%20not%20yet%20visited%20vertex%20(We%20are%20basically%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20%20picking%20an%20edge%20(u%2C%20v)%20from%20remaining%20edges.%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20i%20%3D%20adj%5Bu%5D.iterator()%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20while%20(i.hasNext())%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20v%20%3D%20i.next()%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(visited%5Bv%5D%20%3D%3D%20false)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Add%20the%20vertices%20(u%2C%20v)%20to%20the%20result%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20set.%20We%20make%20the%20vertex%20u%20and%20v%20visited%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20so%20that%20all%20edges%20from%2Fto%20them%20would%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20be%20ignored%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20visited%5Bv%5D%20%3D%20true%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20visited%5Bu%5D%20%20%3D%20true%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Print%20the%20vertex%20cover%0A%20%20%20%20%20%20%20%20for%20(int%20j%3D0%3B%20j%3CV%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(visited%5Bj%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(j%2B%22%20%22)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Driver%20method%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Create%20a%20graph%20given%20in%20the%20above%20diagram%0A%20%20%20%20%20%20%20%20Graph%20g%20%3D%20new%20Graph(7)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(0%2C%201)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(0%2C%202)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(1%2C%203)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(3%2C%204)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(4%2C%205)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(5%2C%206)%3B%0A%20%0A%20%20%20%20%20%20%20%20g.printVertexCover()%3B%0A%20%20%20%20%7D%0A%7D%0A\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>java program &#8211; Vertex Cover Problem &#8211; Introduction and Approximate Algorithm &#8211; It can be proved that the above approximate algorithm never finds a vertex<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,73906,78521],"tags":[79056,79036,79037,79038,79035,79055,79034],"class_list":["post-26538","post","type-post","status-publish","format-standard","hentry","category-coding","category-graph-algorithms","category-hard-problems","tag-edge-cover","tag-minimum-vertex-cover-algorithm-dynamic-programming","tag-minimum-vertex-cover-bipartite-graph","tag-set-cover","tag-vertex-cover-np-complete","tag-vertex-cover-problem-ppt","tag-what-is-a-vertex-cover"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26538","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26538"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26538\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26538"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26538"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26538"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}