{"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 – 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[ad type=”banner”]\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
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[ad type=”banner”]\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<\/pre>\n
Following diagram taken from CLRS book<\/a> shows execution of above approximate algorithm.<\/p>\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
 
 <\/div> 
\/\/ Java Program to print Vertex Cover of a given undirected graphimport java.io.*;import java.util.*;import java.util.LinkedList; \/\/ This class represents an undirected graph using adjacency listclass Graph{    private int V;   \/\/ No. of vertices     \/\/ Array  of lists for Adjacency List Representation    private LinkedList<Integer> adj[];     \/\/ Constructor    Graph(int v)    {        V = v;        adj = new LinkedList[v];        for (int i=0; i<v; ++i)            adj[i] = new LinkedList();    }     \/\/Function to add an edge into the graph    void addEdge(int v, int w)    {        adj[v].add(w);  \/\/ Add w to v's list.        adj[w].add(v);  \/\/Graph is undirected    }     \/\/ The function to print vertex cover    void printVertexCover()    {        \/\/ Initialize all vertices as not visited.        boolean visited[] = new boolean[V];        for (int i=0; i<V; i++)            visited[i] = false;         Iterator<Integer> i;         \/\/ Consider all edges one by one        for (int u=0; u<V; u++)        {            \/\/ An edge is only picked when both visited[u]            \/\/ and visited[v] are false            if (visited[u] == false)            {                \/\/ Go through all adjacents of u and pick the                \/\/ first not yet visited vertex (We are basically                \/\/  picking an edge (u, v) from remaining edges.                i = adj[u].iterator();                while (i.hasNext())                {                    int v = i.next();                    if (visited[v] == false)                    {                         \/\/ Add the vertices (u, v) to the result                         \/\/ set. We make the vertex u and v visited                         \/\/ so that all edges from\/to them would                         \/\/ be ignored                         visited[v] = true;                         visited[u]  = true;                         break;                    }                }            }        }         \/\/ Print the vertex cover        for (int j=0; j<V; j++)            if (visited[j])              System.out.print(j+" ");    }     \/\/ Driver method    public static void main(String args[])    {        \/\/ Create a graph given in the above diagram        Graph g = new Graph(7);        g.addEdge(0, 1);        g.addEdge(0, 2);        g.addEdge(1, 3);        g.addEdge(3, 4);        g.addEdge(4, 5);        g.addEdge(5, 6);         g.printVertexCover();    }}<\/code><\/pre> <\/div>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
java program – 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":[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}]}}