{"id":26518,"date":"2017-12-20T21:31:01","date_gmt":"2017-12-20T16:01:01","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26518"},"modified":"2017-12-20T21:31:01","modified_gmt":"2017-12-20T16:01:01","slug":"c-programming-vertex-cover-problem-introduction-approximate-algorithm","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-vertex-cover-problem-introduction-approximate-algorithm\/","title":{"rendered":"C Programming – Vertex Cover Problem | Set 1 (Introduction and Approximate Algorithm)"},"content":{"rendered":"

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>Although the name is Vertex Cover, the set covers all edges of the given graph. Given an undirected graph, the vertex cover problem is to find minimum size vertex cover<\/strong><\/em>.<\/p>\n

Following are some examples.<\/p>\n

Vertex Cover Problem<\/a> is a known 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 CLRS book<\/a>.<\/p>\n

Approximate Algorithm for Vertex Cover:<\/strong><\/p>\n

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 CLRS book<\/a> shows execution of above approximate algorithm.<\/pre>\n
How well the above algorithm perform?<\/strong>
\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 this <\/a>for proof)<\/p>\n[ad type=\u201dbanner\u201d]\n
C++ program:<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20Program%20to%20print%20Vertex%20Cover%20of%20a%20given%20undirected%20graph%0A%23include%3Ciostream%3E%0A%23include%20%3Clist%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20This%20class%20represents%20a%20undirected%20graph%20using%20adjacency%20list%20%0Aclass%20Graph%0A%7B%0A%20%20%20%20int%20V%3B%20%20%20%20%2F%2F%20No.%20of%20vertices%0A%20%20%20%20list%3Cint%3E%20*adj%3B%20%20%2F%2F%20Pointer%20to%20an%20array%20containing%20adjacency%20lists%0Apublic%3A%0A%20%20%20%20Graph(int%20V)%3B%20%20%2F%2F%20Constructor%0A%20%20%20%20void%20addEdge(int%20v%2C%20int%20w)%3B%20%2F%2F%20function%20to%20add%20an%20edge%20to%20graph%0A%20%20%20%20void%20printVertexCover()%3B%20%20%2F%2F%20prints%20vertex%20cover%0A%7D%3B%0A%20%0AGraph%3A%3AGraph(int%20V)%0A%7B%0A%20%20%20%20this-%3EV%20%3D%20V%3B%0A%20%20%20%20adj%20%3D%20new%20list%3Cint%3E%5BV%5D%3B%0A%7D%0A%20%0Avoid%20Graph%3A%3AaddEdge(int%20v%2C%20int%20w)%0A%7B%0A%20%20%20%20adj%5Bv%5D.push_back(w)%3B%20%2F%2F%20Add%20w%20to%20v%E2%80%99s%20list.%0A%20%20%20%20adj%5Bw%5D.push_back(v)%3B%20%2F%2F%20Since%20the%20graph%20is%20undirected%0A%7D%0A%20%0A%2F%2F%20The%20function%20to%20print%20vertex%20cover%0Avoid%20Graph%3A%3AprintVertexCover()%0A%7B%0A%20%20%20%20%2F%2F%20Initialize%20all%20vertices%20as%20not%20visited.%0A%20%20%20%20bool%20visited%5BV%5D%3B%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3CV%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20visited%5Bi%5D%20%3D%20false%3B%0A%20%0A%20%20%20%20list%3Cint%3E%3A%3Aiterator%20i%3B%0A%20%0A%20%20%20%20%2F%2F%20Consider%20all%20edges%20one%20by%20one%0A%20%20%20%20for%20(int%20u%3D0%3B%20u%3CV%3B%20u%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20An%20edge%20is%20only%20picked%20when%20both%20visited%5Bu%5D%20and%20visited%5Bv%5D%0A%20%20%20%20%20%20%20%20%2F%2F%20are%20false%0A%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%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Go%20through%20all%20adjacents%20of%20u%20and%20pick%20the%20first%20not%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20yet%20visited%20vertex%20(We%20are%20basically%20picking%20an%20edge%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20(u%2C%20v)%20from%20remaining%20edges.%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(i%3D%20adj%5Bu%5D.begin()%3B%20i%20!%3D%20adj%5Bu%5D.end()%3B%20%2B%2Bi)%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%20int%20v%20%3D%20*i%3B%0A%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%7B%0A%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%20set.%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20We%20make%20the%20vertex%20u%20and%20v%20visited%20so%20that%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20all%20edges%20from%2Fto%20them%20would%20be%20ignored%0A%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%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%20break%3B%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%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Print%20the%20vertex%20cover%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3CV%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20if%20(visited%5Bi%5D)%0A%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20i%20%3C%3C%20%22%20%22%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20methods%20of%20graph%20class%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20Create%20a%20graph%20given%20in%20the%20above%20diagram%0A%20%20%20%20Graph%20g(7)%3B%0A%20%20%20%20g.addEdge(0%2C%201)%3B%0A%20%20%20%20g.addEdge(0%2C%202)%3B%0A%20%20%20%20g.addEdge(1%2C%203)%3B%0A%20%20%20%20g.addEdge(3%2C%204)%3B%0A%20%20%20%20g.addEdge(4%2C%205)%3B%0A%20%20%20%20g.addEdge(5%2C%206)%3B%0A%20%0A%20%20%20%20g.printVertexCover()%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n","protected":false},"excerpt":{"rendered":"
C Programming – Vertex Cover Problem – Introduction and Approximate Algorithm – 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":[69866,1,73906,78521,24],"tags":[70483,72848,72992,79036,79037,79038,72853,79039,79035,79040,79034],"class_list":["post-26518","post","type-post","status-publish","format-standard","hentry","category-c-programming","category-coding","category-graph-algorithms","category-hard-problems","category-html","tag-dynamic-programming","tag-dynamic-programming-code-generation-algorithm","tag-dynamic-programming-python","tag-minimum-vertex-cover-algorithm-dynamic-programming","tag-minimum-vertex-cover-bipartite-graph","tag-set-cover","tag-types-of-dynamic-programming","tag-vertex-cover-greedy-algorithm","tag-vertex-cover-np-complete","tag-vertex-cover-problem-example-ppt","tag-what-is-a-vertex-cover"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26518","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=26518"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26518\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26518"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26518"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26518"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}