{"id":3894,"date":"2021-11-19T11:35:47","date_gmt":"2021-11-19T06:05:47","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3894"},"modified":"2021-11-19T11:35:48","modified_gmt":"2021-11-19T06:05:48","slug":"vertex-cover-problem","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/vertex-cover-problem\/","title":{"rendered":"Vertex Cover Problem"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#approach\">Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#naive-approach\">Naive Approach:<\/a><\/li><li><a href=\"#approach-2approximate-algorithm-for-vertex-cover\">Approach 2(Approximate Algorithm for Vertex Cover):<\/a><\/li><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#faqs\">FAQs<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given a graph of <strong>n <\/strong>nodes and <strong>m<\/strong> edges, find its <strong>minimum size vertex cover<\/strong>.<\/p>\n\n\n\n<p><strong>Vertex Cover: <\/strong>The vertex Cover of a graph is defined as a subset of its vertices, such for every edge in the graph, from vertex<strong> u<\/strong> to <strong>v, <\/strong>at least one of them must be a part of the vertex cover set.<\/p>\n\n\n\n<p id=\"-sample-test-cases--\"><strong>Sample Test Cases:<\/strong><\/p>\n\n\n\n<p>Input 1:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"894\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"input 1\"  class=\"wp-image-4031 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-1-1-1024x894.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-1-1-1024x894.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-1-1-300x262.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-1-1-768x670.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-1-1-1536x1341.png 1536w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-1-1-2048x1788.png 2048w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-1-1-380x332.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-1-1-550x480.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-1-1-800x698.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-1-1-1160x1013.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-1-1.png 2265w\" ><\/figure>\n\n\n\n<p>Output 1:<\/p>\n\n\n\n[2, 4]\n\n\n\n<p>Explanation 1:<\/p>\n\n\n\n<p>A valid vertex cover of the graph can be <strong>[2, 4]<\/strong>. <strong>[4, 0]<\/strong> is also a valid vertex cover.<\/p>\n\n\n\n<p>Input 2:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"894\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"input 2\"  class=\"wp-image-4032 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-2-1-1024x894.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-2-1-1024x894.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-2-1-300x262.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-2-1-768x671.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-2-1-1536x1341.png 1536w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-2-1-2048x1788.png 2048w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-2-1-380x332.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-2-1-550x480.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-2-1-800x699.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-2-1-1160x1013.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-2-1.png 2265w\" ><\/figure>\n\n\n\n<p>Output 2:<\/p>\n\n\n\n[0, 1, 3, 4, 5, 6]\n\n\n\n<p>Explanation 2:<\/p>\n\n\n\n<p>The vertex cover for the above graph can be seen to be made of the set <strong>[0, 1, 3, 4, 5, 6]<\/strong>.<\/p>\n\n\n\n<h2 id=\"approach\">Approach<\/h2>\n\n\n\n<p>The vertex cover problem is an NP-Complete problem, which means that there is no known polynomial-time solution for finding the minimum vertex cover of a graph unless it can be proven that <strong>P = NP<\/strong>. There, however, exists polynomial-time approximate algorithms to find the vertex cover of a graph.<\/p>\n\n\n\n<h3 id=\"naive-approach\">Naive Approach:<\/h3>\n\n\n\n<p>We can naively solve the problem by iterating over all the <strong>subsets of the vertices<\/strong> and using only those vertices, forming a new graph containing all the edges contained by these vertices. Then we can check if this new graph, contains all the edges of the original graph or not based on which it can be a <strong>candidate for the vertex cover.<\/strong> Out of all the candidates, we print the set, which has the <strong>minimum<\/strong> size.<\/p>\n\n\n\n<p>This naive approach will have an <strong>exponential<\/strong> runtime complexity.<\/p>\n\n\n\n<h3 id=\"approach-2approximate-algorithm-for-vertex-cover\">Approach 2(Approximate Algorithm for Vertex Cover):<\/h3>\n\n\n\n<p>The algorithms which are of interest to us in lieu of the vertex cover problem are the approximation algorithms that run in <strong>polynomial time complexity<\/strong>. A simple approximate algorithm for the vertex cover problem is described below:<\/p>\n\n\n\n<ul><li>Initialize the vertex cover set as <strong>empty<\/strong>.<\/li><li>Let the set of all edges in the graph be called <strong>E.<\/strong><\/li><li>While <strong>E<\/strong> is not empty:<ul><li>Pick a random edge from the set <strong>E<\/strong>, add its constituent nodes, <strong>u<\/strong> and <strong>v<\/strong> into the vertex cover set.<\/li><li>For all the edges, which have either <strong>u <\/strong>or <strong>v<\/strong> as their part, remove them from the set <strong>E<\/strong>.<\/li><\/ul><\/li><li>Return the final obtained vertex cover set, after the set <strong>E<\/strong> is empty.<\/li><\/ul>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"629\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Pseudo Code\"  class=\"wp-image-4033 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Pseudo-Code-1024x629.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Pseudo-Code-1024x629.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Pseudo-Code-300x184.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Pseudo-Code-768x472.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Pseudo-Code-380x233.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Pseudo-Code-550x338.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Pseudo-Code-800x492.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Pseudo-Code.png 1149w\" ><\/figure>\n\n\n\n<p class=\"has-text-align-center\"><strong>Pseudo Code for the above algorithm<\/strong><\/p>\n\n\n\n<p>It can be proven that the above algorithm will always find a vertex cover that is never greater than twice the size of the optimal vertex cover for the given graph.<\/p>\n\n\n\n<p id=\"-implementationcode-\"><strong>Implementation\/Code:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">void vertexCover(vector &amp;lt; int &amp;gt; edges[], int n, int m) {\n  vector &amp;lt; bool &amp;gt; vis(n, false);\n  for (int i = 0; i &amp;lt; n; i++) {\n    if (!vis[i]) {\n      for (auto x: edges[i]) {\n        if (!vis[x]) {\n          vis[x] = true;\n          vis[i] = true;\n          break;\n        }\n      }\n    }\n  }\n  for (int i = 0; i &amp;lt; n; i++) {\n    if (vis[i]) {\n      cout &amp;lt;&amp;lt; i &amp;lt;&amp;lt; \" \";\n    }\n  }\n  cout &amp;lt;&amp;lt; endl;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static void vertexCover(LinkedList &amp;lt; Integer &amp;gt; edges[], int n, int m) {\n  boolean[] vis = new boolean[n];\n  Arrays.fill(vis, false);\n  for (int i = 0; i &amp;lt; n; i++) {\n    if (!vis[i]) {\n      for (Integer x: edges[i]) {\n        if (!vis[x]) {\n          vis[x] = true;\n          vis[i] = true;\n          break;\n        }\n      }\n    }\n  }\n  for (int i = 0; i &amp;lt; n; i++) {\n    if (vis[i]) {\n      System.out.print(i + \" \");\n    }\n  }\n  System.out.println();\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def vertexCover(edges, n, m):\n    vis = [False] * n\n    for i in range(n):\n        if not vis[i]:\n            for x in edges[i]:\n                if not vis[x]:\n                    vis[x] = True\n                    vis[i] = True\n                    break\n    for i in range(n):\n        if vis[i]:\n            print(i, end=\" \")\n    print()<\/pre>\n\n\n\n<p><strong>Complexity Analysis:<\/strong><\/p>\n\n\n\n<ul><li>Time Complexity: O(n + m) \/\/ n = number of nodes, m = number of edges<\/li><li>Space Complexity: O(n)<\/li><\/ul>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<p><strong>1. Can the vertex cover problem be solved in polynomial time if there are some constraints on the graphs?<\/strong><\/p>\n\n\n\n<p>A. Yes, it can be solved in polynomial time for <strong>Trees<\/strong> and <strong>Bipartite Graphs<\/strong>.<\/p>\n\n\n\n<p><strong>2. What algorithms are used to solve the vertex cover problem for bipartite graphs?<\/strong><\/p>\n\n\n\n<p>A. <strong>Flows<\/strong> can be used to solve the vertex cover problem for bipartite graphs.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a graph of n nodes and m edges, find its minimum size vertex cover. Vertex&hellip;\n","protected":false},"author":5,"featured_media":4034,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[580],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3894"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3894"}],"version-history":[{"count":4,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3894\/revisions"}],"predecessor-version":[{"id":4035,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3894\/revisions\/4035"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/4034"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3894"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3894"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3894"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}