My Math Forum Approximated vertex cover algorithm on random graph

 Computer Science Computer Science Forum

 December 13th, 2017, 09:58 AM #1 Member   Joined: Mar 2015 From: USA Posts: 34 Thanks: 1 Approximated vertex cover algorithm on random graph I'm trying to investigate the results of running the following factor two algorithm for minimum vertex cover on random graphs. To be more specific, for a given number of vertices $n$ I'm trying to find the smallest $p$ so that running the approximation algorithm above on a random graph $G(n,p)$ will give me (with high probability) a vertex cover with a size that is less then 80% from $n$. For example, I run some tests in java with this algorithm implementation and found: For a graph with 60 vertices- $p<9$% will give the desired results. For a graph with 300 vertices - $p<0.7$% will give the desired results. For a graph with 3500 vertices - $p<0.3$% will give the desired results. As it can be seen, the larger the number of vertices - the smaller the number of $p$ needed for my desired results. My try for explaining those results: since in a graph $G(V,E)$ we know that $|E| = O(V^2)$ , if we enlarge $|V|$ then the number of possibilities for edges will be much greater relative to the enlargement of $|V|$. Therefore, if we have graphs $G(n,p), G'(n' , p)$ when $n'>n$ then it's more likely that $G'$ will contain more edges. Let's denote by $c^*$ and $c'^*$ the minimal vertex cover of $G$ and $G'$, and by $c$ and $c'$ the approximated vertex cover of $G$ and $G'$. Since their edges were randomly selected and we have more edges in $G'$ - it's more likely that $c^*/n < c'^*/n$ and therefore also $c/n < c'/n$. There are few things I'm not sure about: 1. The last line of the explanation when I wrote that the fact that the edges where randomly selected help us deduce the desired results. Is my explanation correct? 2. It seems that my results are relating to a general vertex cover, and are not specific only for the approximated algorithm. Am I right here?

 Tags algorithm, approximated, cover, graph, random, vertex

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post mathsman1 Math 3 November 30th, 2015 11:37 AM kayna84 Pre-Calculus 1 July 30th, 2015 11:44 AM vinaychaturvedi Computer Science 0 April 25th, 2012 03:45 AM Singularity Applied Math 1 April 15th, 2011 06:42 AM hkoehler Computer Science 0 May 16th, 2010 07:37 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top