
Computer Science Computer Science Forum 
 LinkBack  Thread Tools  Display Modes 
December 13th, 2017, 10:58 AM  #1 
Member Joined: Mar 2015 From: USA Posts: 33 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  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
How many mathematics textbooks is it realistic to study cover to cover  mathsman1  Math  3  November 30th, 2015 12:37 PM 
Standard form and identify the vertex of a graph  kayna84  PreCalculus  1  July 30th, 2015 12:44 PM 
Hamiltonian Algorithm for n vertex complete graph  vinaychaturvedi  Computer Science  0  April 25th, 2012 04:45 AM 
Number of ways to make a graph from nsize vertex set  Singularity  Applied Math  1  April 15th, 2011 07:42 AM 
Weighted Vertex Cover on Bipartite Graph  NPhard?  hkoehler  Computer Science  0  May 16th, 2010 08:37 PM 